Dijkstra’s Algorithm can be applied to either a directed or an undirected graph to find the shortest path to each vertex from a single source. It can only be used with non-negative edge weights.

A table is generated to track the distance from the source (S) vertex. The distance to each vertex is initialized to infinity except for the source itself. Another variable, π, is used to track the previous vertex from which the specified vertex was reached.

Dijkstra’s algorithm starts with the source, S, and relaxes the edges that are connected directly to it in alphabetical order. The first edge to be relaxed is S to A. The value for A is updated from infinity to 5 and the predecessor is updated to S. The edge S-A is also marked as complete.

Next, the edge S-I is relaxed. The distance to I is updated to 15 and the predecessor is marked as S. The edge S-I is marked as visited. All of the outbound edges from S have been visited, so S is marked as completed.

Dijkstra’s algorithm moves from vertex S to vertex A. Vertex A is the chosen since it’s the closest, visited vertex to the source. The same process is repeated: all of the immediate, outbound vertices are visited from vertex A. Those vertices are C and E. Vertex C is visited first since it comes first alphabetically. The distance to C is updated to 8 since vertex A can be reached in 5 units and vertex C can be reached in another 3 units. The predecessor is set to A and the edge A-C is marked as visited.

Vertex E is visited next. The distance to vertex E is updated to 7 (S-A-5 + A-E-2) and the predecessor of E is updated to A. Since all of the outbound edges from A have been visited, vertex A is marked as complete.

Dijkstra’s algorithm chooses the next closest vertex. Vertex I is currently 15 units away from the source, vertex E is 7 units away and vertex C is 8 units away. Vertex E is the closest, so it’s chosen next. Since there are no outbound edges from vertex E, it is marked as complete.

Since vertex C is 8 units away and vertex I is 15 units away, vertex C is chosen next. Vertex C has 3 outbound edges: C-B, C-D, and C-H. Vertex B is visited first since it’s alphabetically the next one on the list. The distance to B is updated to 15 (S-A-C-8 + C-B-7) and the predecessor is set as C. The edge C-B is marked as visited.

Dijkstra’s algorithm visits vertex D next. The distance to vertex D is updated to 14 (S-A-C-8 + C-D-6) and the predecessor of D is set as C. The edge C-D is marked as visited.

The last outbound edge from C, edge C-H, is visited. The distance to vertex H is updated to 11 (S-A-C-8 + C-H-3) and the predecessor to H is updated to C. Since all the outbound edges have been visited from C, vertex C is marked as complete.

Dijkstra’s algorithm chooses the next vertex. Vertex I is 15 units away from the source, vertex B is 15 units away, vertex D is 14 units away, and vertex H is 11 units away. Since vertex H is the closest vertex to the source, it is chosen next. Vertex H has two outbound edges: H-C and H-D. Vertex C is visited first. Vertex C can already be reached in 8 units so there is no point to reach it in 20 units. The distance to vertex C stays the same and the edge H-C is marked as visited.

Vertex D is visited next via edge H-D. Since the distance to vertex D via edge H-D (12 units) is shorter than the distance to vertex D via edge C-D (14), the distance to vertex D is updated to 12; the predecessor to vertex D is updated to H. The edge H-D is marked as complete; since all the outbound edges from H have been visited, H is marked as complete.

Dijkstra’s algorithm chooses the next closest edge by examining all the available, non-visited vertices. Vertex I can be reached in 15 units, D can be reached in 12 units and B can be reached in 15 units. Since D is the closest vertex to the source, vertex D is chosen. Vertex D has one outbound edge, D-I. The distance to vertex I from D is 14. Since vertex I can be reached in 14 units via edge D-I, the distance to vertex I is updated to 14 and the predecessor is set to D. Edge D-I is marked as visited. All of the outbound edges from vertex D have been visited and vertex D is marked as complete.

Dijkstra’s algorithm examines all the edges that can be visited. Vertex I is 14 units away and vertex B is 15 units away. Since vertex I is the closest one to the source, vertex I is chosen next.

Vertex I has no outbound edges so vertex I is marked as complete. Vertex B is the only other available, non-visited edge from the source, so vertex B is chosen next.

Vertex B has one outbound edge: B-F. Vertex F can be reached in 19 units
(S-A-C-B-15 + B-F-4). The distance to F is updated to 19 and the predecessor is set to B. The edge B-F is marked as visited and since there are no other outbound edges from vertex B, it is marked as complete.

Vertex F is the next closest vertex to the source. Vertex F has one outbound edge, F-G. Vertex G can be reached in 21 units. The distance to G is updated to 21 and the predecessor of G is set to F. The edge F-G is marked as visited and since there are no other outbound edges from F, vertex F is marked as complete.

Vertex G is the last unvisited vertex. Vertex G has one outbound edge, from G to B. The distance to vertex G through edge G-B is 21 units. Since the distance to B through edge C-B is closer than through edge G-B, the distance to B is kept at 15. The edge G-B is marked as visited and since all the outbound edges from G have been visited, vertex G is marked as complete. All the vertices in the directed graph have been visited, so Dijkstra’s algorithm is finished. The list below shows the shortest path to each vertex from the source.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.