Dijkstra's shortest path algorithm

Dijkstra's algorithm finds the shortest paths from one source vertex to all other vertices in a weighted graph with non-negative edge weights. It is greedy: it repeatedly selects the unvisited vertex with the smallest known distance, finalises it, and relaxes (updates) the distances of its neighbours.

Algorithm

DIJKSTRA(G, s)
1. for each vertex v: dist[v] = infinity, prev[v] = none
2. dist[s] = 0;  S = empty set
3. while S does not contain all vertices
4.     u = vertex not in S with minimum dist[u];  add u to S
5.     for each neighbour v of u not in S
6.         if dist[u] + w(u,v) < dist[v]
7.             dist[v] = dist[u] + w(u,v);  prev[v] = u

Time: O(V²) with an array, O(E log V) with a binary heap.

Example

Undirected graph with edges A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2. Source = A.

Shortest paths from A:

• A to C: 2 (A-C)
• A to B: 3 (A-C-B)
• A to D: 8 (A-C-B-D)
• A to E: 10 (A-C-B-D-E)

Dijkstra fails with negative edge weights (Bellman-Ford is used instead).