Dijkstra Shortest Path
Dijkstra's algorithm finds the shortest distance from a single source to every other node in a graph with non negative edge weights. It generalizes BFS to handle edges of differing cost.
How it works
Keep a tentative distance for every node, starting at zero for the source and infinity for the rest. Use a priority queue ordered by distance so you always expand the closest unfinalized node next. For that node:
- Mark its distance as final, since with non negative weights no shorter path can appear later.
- Relax each outgoing edge: if reaching a neighbor through this node is cheaper than its current best, update the neighbor and push it onto the queue.
Repeat until the queue empties. Recording which node updated each distance lets you reconstruct the actual paths.
Why non negative
The greedy step trusts that the closest unfinalized node is truly done. A negative edge could later create a cheaper route, breaking that guarantee, so Dijkstra requires non negative weights and the Bellman Ford algorithm handles negatives instead.
With a binary heap, the runtime is roughly the number of edges times a logarithmic factor.
Key idea
Dijkstra greedily finalizes the nearest node and relaxes its edges, finding shortest paths whenever edge weights are non negative.