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.
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.
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.
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.
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.
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
.jpeg)
.jpeg)
.jpeg)
.jpeg)