Dijkstra's Algorithm

5 min read#networks#algorithms#weighted

Find the cheapest route in a weighted graph by greedily settling the nearest unfinished node, one at a time.

Contents

Dijkstra's Algorithm

When the edges of a Graph carry weights — miles of road, minutes of travel, dollars of cost — the shortest path is no longer the one with the fewest hops. A route of three long edges may cost more than five short ones. Dijkstra's algorithm solves this single-source shortest path problem on graphs with non-negative weights, and it does so with one elegant idea: always finish the closest node you have not yet finished.

It is best understood as Breadth-First Search upgraded for weights. BFS expands a uniform wavefront because every edge costs 1; Dijkstra expands a wavefront that bulges where edges are cheap and lags where they are expensive — and to keep the closest frontier node always at hand, it swaps BFS's plain queue for a priority queue.

The greedy frontier

Each node holds a tentative distance: the best total cost found to it so far, starting at \infty for all but the source. The algorithm repeatedly:

  1. Picks the unfinished node u with the smallest tentative distance and marks it settled — its distance is now final.
  2. Relaxes each edge u \to v: if reaching v through u is cheaper than v's current tentative distance, lower it.

With a binary-heap priority queue the whole thing runs in O((V + E)\log V).

The wavefront, weighted

Below, each grid cell carries a random terrain cost (darker cells are slow, expensive ground). Dijkstra grows its settled region outward from the center, but instead of a clean diamond like BFS, the frontier races through cheap terrain and crawls through costly patches. Brightness shows the final shortest-path cost to each settled cell — the contour lines of cost bend around the expensive regions exactly as water finds the path of least resistance.

Dijkstra settling outward over costly terrain. The frontier rushes through cheap ground and stalls in expensive ground; color shows total cost from the center. Re-runs from a new random landscape.

Cousins and uses

Dijkstra is the engine inside every routing system — road navigation, network packet routing, game pathfinding. Add a heuristic that estimates remaining distance and it becomes A*, which steers the frontier toward a goal instead of growing in all directions. Strip the weights back to a constant and it degenerates exactly into Breadth-First Search. And though it answers a different question — cheapest route between two points — it shares its greedy, frontier-growing spirit with the algorithms behind the Minimum Spanning Tree, which instead seek the cheapest way to connect everything.

See also