Week 5: Graph Algorithms
Week 5
Mid-term Test
Nerdy Things You Should Know
Directed Graphs
Directed Graphs (Digraphs)
Digraph Applications
Digraph Representation
Reachability
Transitive Closure
Digraph Traversal
Example: Web Crawling
Weighted Graphs
Weighted Graphs
Weighted Graph Representation
Minimum Spanning Trees
Minimum Spanning Trees
Kruskal's Algorithm
Prim's Algorithm
Sidetrack: Priority Queues
Other MST Algorithms
Shortest Path
Shortest Path
Single-source Shortest Path (SSSP)
Edge Relaxation
Dijkstra's Algorithm
All-pair Shortest Path (APSP)
Floyd's Algorithm
Network Flow
Flow Networks
Augmenting Paths
Residual Network
Edmonds-Karp Algorithm
Digraph Applications
PageRank
Summary
Produced: 26 Jun 2020
![[index]](icon/up.gif){kind=icon}