Demystifying the Shortest Path Algorithm with Example

Demystifying the Shortest Path Algorithm with Examples

Saturday 05 October 2024

Consider the complete network in Fig. 1, to find the shortest path from A to H using the Dijkstra algorithm [1]. A simple inspection reveals the optimal path ABEFGH with cost 10. However, implementing the algorithm through a computer program deserves some attention. 

Figure 1 

The procedure excerpt from [2]. 

Step1. A is marked. The nodes connected directly to A are labeled with (cost, from node). All other nodes in the network are labeled with (infinity, dash). B is marked for the next step due to lower cost than C, Fig. 2.

Figure 2

Step2. The nodes connected directly to B are relabeled with (cost, from node). E is marked for the next step due to lower cost than C and D, Fig. 3.

Figure 3

Step3. The nodes connected directly to E are relabeled with (cost, from node). F is marked for the next step due to lower cost than C and D. 

Step4. The modes connected directly to F are relabeled with (cost, from node). G is marked.

Step5. Figure 4 shows the optimal path from A to H: ABEFGH.

Figure 4

There are a lot of posts on the net. A good one is [3]. The Python code was modified for the above example and results are shown in Fig. 5. 

Figure 5

References: 

[1] Dijkstra (1959), [2] CN 6th Tanenbaum, [3] www.dougmahugh.com/dijkstra

Appendix: Output 

Reading the input file ...
('A', 'B', 2.0)
('A', 'C', 6.0)
('B', 'D', 7.0)
('B', 'E', 2.0)
('C', 'E', 1.0)
('C', 'G', 4.0)
('D', 'F', 3.0)
('D', 'H', 3.0)
('E', 'F', 2.0)
('F', 'G', 2.0)
('G', 'H', 2.0)
Building Adjacency List ...
{'C': {('E', 1.0), ('G', 4.0)}, 'F': {('G', 2.0)}, 'G': {('H', 2.0)}, 
'A': {('C', 6.0), ('B', 2.0)}, 'H': set(), 'E': {('F', 2.0)}, 
'B': {('D', 7.0), ('E', 2.0)}, 'D': {('F', 3.0), ('H', 3.0)}}
Unvisited Nodes ...
{'C', 'F', 'G', 'A', 'H', 'E', 'B', 'D'}
Distance from Start Node
{'C': inf, 'F': inf, 'G': inf, 'A': 0, 'H': inf, 'E': inf, 'B': inf, 'D': inf}
Current node =  A
	Unvisited nodes =  {'C', 'F', 'G', 'H', 'E', 'B', 'D'}
		neighbor =  C  distance =  6.0
			New path =  6.0
		neighbor =  B  distance =  2.0
			New path =  2.0
Current node =  B
	Unvisited nodes =  {'C', 'F', 'G', 'H', 'E', 'D'}
		neighbor =  D  distance =  7.0
			New path =  9.0
		neighbor =  E  distance =  2.0
			New path =  4.0
Current node =  E
	Unvisited nodes =  {'C', 'F', 'G', 'H', 'D'}
		neighbor =  F  distance =  2.0
			New path =  6.0
Current node =  C
	Unvisited nodes =  {'F', 'G', 'H', 'D'}
		neighbor =  E  distance =  1.0
		neighbor =  G  distance =  4.0
			New path =  10.0
Current node =  F
	Unvisited nodes =  {'G', 'H', 'D'}
		neighbor =  G  distance =  2.0
			New path =  8.0
Current node =  G
	Unvisited nodes =  {'H', 'D'}
		neighbor =  H  distance =  2.0
			New path =  10.0
Current node =  D
	Unvisited nodes =  {'H'}
		neighbor =  F  distance =  3.0
		neighbor =  H  distance =  3.0
Current node =  H
	Unvisited nodes =  set()
graph definition file: simple_graph3.txt
      start/end nodes: A -> H
        shortest path: ['A', 'B', 'E', 'F', 'G', 'H']
       total distance: 10