[prev] 87 [next]

Summary

  • Digraphs, weighted graphs: representations, applications
  • Reachability
    • Warshall
  • Minimum Spanning Tree (MST)
    • Kruskal, Prim
  • Shortest path problems
    • Dijkstra (single source SPP)
  • Flow networks
    • Edmonds-Karp (maximum flow)

  • Suggested reading (Sedgewick):
    • digraphs … Ch. 19.1-19.3
    • weighted graphs … Ch. 20-20.1
    • MST … Ch. 20.2-20.4
    • SSP … Ch. 21-21.3
    • network flows … Ch. 22.1-22.2