Dijkstra’s Algorithm for finding shortest path in graph

8 min readJan 20, 2023

Dijkstra’s algorithm is used for finding shortest path between graph nodes of any number. From each node say a source node to all the other nodes in graph (it could be directed or undirected graph) a minimum path will be found out using this algorithm. (Here, nodes are denoted for vertices)

Steps for using this algorithm:

STEP 1: First, consider N = source node of graph.

STEP 2: Make a table which carry the distance of all nodes from N node (which is the source node). If no edge is connected between any two nodes of graph than consider it as Infinity (∞).

STEP 3: After making the table, find the node with minimum distance value, and now consider that node as N.

STEP 4: Repeatedly follow the same procedure to find minimum distance from new N to all other nodes using formulae:

= min(D(a), D(b) + D(b,a))

Here a is the node for which distance needs to be calculates ; b carries the value of N node & b,a carry the distance between node b to a if no such put ∞.

STEP 5: Find & fill the table till all values are used in a graph.

STEP 6: At last, a shortest path graph is created with the table created.

Example for better understanding of the algorithm:

Using Undirected graph with 8 nodes (A, B, C, D, E, F, G, H) and 13 Edges as shown below:

Let us consider A is the source node which is N = A, and we need to find the shortest path from source node A to every other node in a graph.

Initial values from A to all other nodes.

In the above table, there is no direct path from A to D, E, F, G & H so, it is initialized with ∞.

Now, from this D(B) = 2; where D is the distance, D(B) is minimum distance from all the nodes.

So, considering D(B) to calculate minimum distance from A to other nodes now using a formulae described in STEP 4 of above algorithm:

= min(D(a), D(b) + D(b,a))

1. Path for node C: = min(D(C), D(B) + D(B,C)); here a is C and b is B according to the formulae.

= min(7, 2 + 4) => min(7, 6) => 6 so now, 6 is minimum distance from A to C through B.

2. Path for node D: = min(D(D), D(B) + D(B,D)); here a is Dand b is B according to the formulae.

= min(∞, 2 + 8) => min(∞, 10) => 10 so now, 10 is minimum distance from A to D through B.

3. Path for node E: = min(D(E), D(B) + D(B,E)); here a is E and b is B according to the formulae.

= min(∞, 2 + 6) => min(∞, 8) => 8 so now, 8 is minimum distance from A to E through B.

4. Path for node F: = min(D(F), D(B) + D(B,F)); here a is F and b is B according to the formulae.

= min(∞, 2 + ∞) => min(∞, ∞) => ∞ so now, ∞ is minimum distance from A to F through B, as there is no such path.

5. Path for node G: = min(D(G), D(B) + D(B,G)); here a is G and b is B according to the formulae.

= min(∞, 2 + ∞) => min(∞, ∞) => ∞ so now, ∞ is minimum distance from A to G through B, as there is no such path.

6. Path for node H: = min(D(H), D(B) + D(B,H)); here a is H and b is B according to the formulae.

= min(∞, 2 + ∞) => min(∞, ∞) => ∞ so now, ∞ is minimum distance from A to H through B, as there is no such path.

Regenerate the table with N = B:

In the above table, B is now initialized to ‘-’ as no value because its minimum distance is found from A which is 2.

Now, from this D(C) = 6 which is minimum distance from all the nodes.

So, considering D(C) to calculate minimum distance from A to other nodes now using a formulae described.

Path for node D: = min(D(D), D(C) + D(C,D)); here a is D and b is C according to the formulae.

= min(10, 6 + 11) => min(10, 17) => 10 so, 10 is minimum distance from A to D through B only, as from C it shows the distance of 17 which is not the minimum distance.

2. Path for node E: = min(D(E), D(C) + D(C,E)); here a is E and b is C according to the formulae.

= min(8, 6 + ∞) => min(8, ∞) => 8 so, 8 is minimum distance from A to D through B only, as from C it shows the distance of ∞ which is not the minimum distance.

3. Path for node F: = min(D(F), D(C) + D(C,F)); here a is F and b is C according to the formulae.

= min(∞, 6 + ∞) => min(∞, ∞) => ∞ so, ∞ is minimum distance from A to F through C also, as there is no such path.

4. Path for node G: = min(D(G), D(C) + D(C,G)); here a is G and b is C according to the formulae.

= min(∞, 6+ ∞) => min(∞, ∞) => ∞ so now, ∞ is minimum distance from A to G through C, as there is no such path.

5. Path for node H: = min(D(H), D(C) + D(C,H)); here a is H and b is C according to the formulae.

= min(∞, 6 + ∞) => min(∞, ∞) => ∞ so now, ∞ is minimum distance from A to H through C, as there is no such path.

Make the table with N = C:

From the above table D(E) = 8 which is minimum distance from all the nodes.

So, considering D(E) to calculate minimum distance from A to other nodes now using a formulae described.

Path for node D: = min(D(D), D(E) + D(E,D)); here a is D and b is E according to the formulae.

= min(10, 8 + 2) => min(10, 10) => 10 so, 10 is minimum distance from A to D through B only, distance from E is also 10, so any node can be considered.

2. Path for node F: = min(D(F), D(E) + D(E,F)); here a is F and b is E according to the formulae.

= min(∞, 8 + 5) => min(∞, 13) => 13 so, 13 is minimum distance from A to F through E.

3. Path for node G: = min(D(G), D(E) + D(E,G)); here a is G and b is E according to the formulae.

= min(∞, 8 + 9) => min(∞, 17) => 17 so, 17 is minimum distance from A to G through E.

4. Path for node H: = min(D(H), D(E) + D(E,H)); here a is H and b is E according to the formulae.

= min(∞, 8 + ∞) => min(∞, ∞) => ∞ so now, ∞ is minimum distance from A to H through E, as there is no such path.

Make the table with N = E:

Here, from above table D(D) = 10 has minimum distance from all other nodes.

So, considering D(D) to calculate minimum distance from A to other nodes now using a formulae described.

Path for node F: = min(D(F), D(D) + D(D,F)); here a is F and b is D according to the formulae.

= min(13, 10 + 3) => min(13, 13) => 13 so, 13 is minimum distance from A to F through E only, distance from D is also 13, so any node can be considered.

2. Path for node G: = min(D(G), D(D) + D(D,G)); here a is G and b is D according to the formulae.

= min(17, 10 + ∞) => min(17, ∞) => 17 so, 17 is minimum distance from A to G through E, as there is no path from D.

3. Path for node H: = min(D(H), D(D) + D(D,H)); here a is H and b is D according to the formulae.

= min(∞, 10 + ∞) => min(∞, ∞) => ∞ so, ∞ is minimum distance from A to H through D, as there is no path.

Generate table with N = D:

Here, from above table D(F) = 13 has minimum distance from all other nodes.

So, considering D(F) to calculate minimum distance from A to other nodes now using a formulae described.

Path for node G: = min(D(G), D(F) + D(F,G)); here a is G and b is F according to the formulae.

= min(17, 13 + 10) => min(17, 23) => 17 so, 17 is minimum distance from A to G through E only.

2. Path for node H: = min(D(H), D(F) + D(F,H)); here a is H and b is F according to the formulae.

= min(∞, 13 + 1) => min(∞,14) => 14 so, 14 is minimum distance from A to H through F.

Make table with N = F:

Now, minimum distance is D(H) = 14.

Path for node G: min(D(G), D(H) + D(H,G)); here a is G and b is H according to the formulae.

= min(17, 14 + 9) => min(17, 21) => 17 so, 17 is minimum distance from A to G through E only.

At last, only node G remains and minimum distance from A to all other nodes is utilized.

Final table with minimum distances:

Final table with all nodes as source node and minimum distance from A to all other nodes.

For better understanding:

Shortest path graphs with minimum distance:

There could be more than one graphs with shortest distance as some nodes have same distance from different nodes like D and F has two different path with same minimum distance.