Dijkstra's Shortest Path

Find shortest paths from a source in graphs with non-negative edge weights. Greedy picks the closest unvisited node; optimality follows from triangle inequality and non-negative edges.

Algorithm Steps

Initialize distances to ∞ except source = 0.
Pick the unvisited vertex with the smallest distance.
Relax its outgoing edges.
Repeat until all vertices visited.

Speed (ms)

Nodes

Pseudocode

1procedure DIJKSTRA(G, source)
2  for each vertex v do dist[v] ← ∞; dist[source] ← 0
3  visited ← ∅
4  repeat |V| times:
5    u ← unvisited vertex with minimum dist
6    mark u visited
7    for each edge (u, v, w) outgoing from u do
8      if dist[u] + w < dist[v] then
9        dist[v] ← dist[u] + w
10      end if
11    end for
12  end repeat
13end procedure

Practice Problems

Use Cases

GPS navigation and routing on road networks.
Network packet routing with non-negative costs.
Game AI pathfinding on static, weighted maps.

Back to Prim's MST Next: Gas Station