The idea
Dijkstra’s algorithm finds the shortest distance from one start vertex to every other vertex. All edge weights must be non-negative.
Keep dist[u], the best distance known so far, and a min-priority queue of pairs (distance, vertex). Pop the closest unfinished vertex: its distance is final, because any other route would pass through a vertex at least as far away. Then try to improve its neighbours.
With a priority queue the cost is O((V + E) log V).
Sample problem
743. Network Delay Time ↗ Medium
A signal is sent from node k through a network of directed edges, each with a travel time. Return the time at which the last node receives it, or −1 if some node never does.
times = [[1,2,4],[1,3,1],[3,2,2],[2,4,1],[3,4,5],[4,5,3]], n = 5, k = 1 output = 7
Why the solution works
Each node first hears the signal along its shortest path from k, so the answer is the largest shortest-path distance.
Dijkstra’s algorithm finalises nodes in order of distance. The closest unfinished node cannot be improved: any other route would pass through a node at least as far away, and edges never have negative time.
A min-priority queue hands over that closest node. Outdated queue entries are skipped by comparing them with the best known distance.
Complexity: O((V + E) log V) time, O(V + E) memory.
Watch out
- A negative edge breaks the argument that a popped distance is final.
- Skip stale queue entries, or the running time degrades badly.
- Distances can exceed
int: uselong long, and a min-heap (greater<>).