Sign in to watch this lesson
Algorithms - Graphs II · 4:38
Dijkstra
When links have latencies instead of equal costs, hop counting fails, and Dijkstra's algorithm finds the lowest-latency route from one gateway to all others: repeatedly mark the unmarked vertex with the smallest label and relax its edges. We run it on a five-gateway graph (distances 0 3 1 4 7, route 0 2 1 3 4), prove each label is final when marked with the frontier-wall argument, implement the dense O(n^2 + m) version that is optimal when m is close to n^2, and break it with a single negative rebate link.
You will learn
- Run Dijkstra's algorithm by hand: labels, marking the closest unmarked vertex, relaxing its edges
- Prove that a label is final the moment its vertex is marked, and point to the single step that needs non-negative weights
- Implement the dense O(n^2 + m) version with parent pointers and 64-bit distances, and know when it beats a heap
- Construct a graph with one negative edge on which Dijkstra reports a wrong distance