Dijkstra's algorithm
The conceptHow a map app picks the fastest route out of millions
Dijkstra's algorithm finds the shortest route from one start to every point in a graph with weighted edges, like roads labelled in minutes. Each round it settles the unsettled point with the smallest known distance.
Example: Home→A 2, Home→B 7, A→B 3, A→Work 8, B→Work 1. Settling Home gives A 2 and B 7. Settling A drops B to 5 and gives Work 10. Settling B drops Work to 6: the route is Home→A→B→Work.
Lowering a neighbour's best distance like this is called relaxing an edge. Breadth-first search counts hops, which is only right when every edge costs the same; Dijkstra adds up the real weights.
What it’s forRelaxes an edge: checks whether reaching v through u beats the best route to v found so far.
dist(v) ← min(dist(v), dist(u) + w(u,v))
- dist(v)
- best distance to junction v found so far, starting at ∞
- u
- the junction just settled, the one with the smallest distance
- w(u,v)
- weight of the road from u to v, e.g. minutes of driving; must be ≥ 0
What it givesAn updated best-known distance for v, which only ever goes down.
- dist(B) = 7, dist(A) = 2, w(A,B) = 3
- 2 + 3 = 5, and min(7, 5) = 5
- So B's best distance drops from 7 to 5, via A