Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a starting node to every other node in a weighted graph — as long as no edge has a negative weight. It works greedily: always finalize the closest unfinished node next.

The greedy insight

Keep a tentative shortest distance to every node (∞ at first, 0 for the source). Repeatedly pick the unvisited node with the smallest tentative distance, lock it in as final, and *relax* its neighbours — if going through this node is cheaper, update their distance.

1. 1Set dist[source] = 0, everything else ∞.
2. 2Pick the unvisited node u with the smallest dist (a priority queue makes this fast).
3. 3Mark u visited — its distance is now final.
4. 4For each neighbour v: if dist[u] + weight(u,v) < dist[v], update dist[v].
5. 5Repeat until every node is visited.