Geography Reference
In-Depth Information
Table 6.3
Starting table and table after each iteration of Dijkstra's shortest path algorithm
Starting table
After iteration 1
After iteration 2
N
Distance
Parent
Included
N
Distance
Parent
Included
N
Distance
Parent
Included
1
•
N1
0
-
Y
1
0
-
Y
2
•
N
2
1.915
1
N
2
1.915
1
N
3
•
N3
•
N3
•
N
4
•
N
4
1.566
1
N
4
1.566
1
N
5
•
N
5
1.228
1
N
5
1.228
1
Y
6
•
N6
•
N
6
3.172
5
N
After iteration 3
After iteration 4
After iteration 5
N
Distance
Parent
Included
N
Distance
Parent
Included
N
Distance
Parent
Included
1
0
-
Y
1
0
-
Y
1
0
-
Y
2
1.915
1
N
2
1.915
1
Y
2
1.915
1
Y
3
3.061
4
N
3
2.805
2
N
3
2.805
2
N
4
1.566
1
Y
4
1.566
1
Y
4
1.566
1
Y
5
1.228
1
Y
5
1.228
1
Y
5
1.228
1
Y
6
2.634
4
N
6
2.634
4
N
6
2.634
4
Y
Firstly, the distance from node 1 is set to 0, as it is the source node. h e 'Included'
entry for node 1 is set to Y, to indicate it is part of the shortest path (obviously it must
be as it is the source node!). Node 1 is connected to nodes 2, 4, and 5, and the distances
from node 1 to these nodes are smaller than ini nity and so replace the existing entries in
the distance column. h e parent nodes for nodes 2, 4, and 5 are set to 1. h e result is the
table 'At er iteration 1' (where each iteration represents a single cycle in the process).
h e shortest distance for any node that has not yet been included is that for node 5
(a distance of 1.228) and this node is now included. Node 5 is connected to two nodes
down the path from node 1: nodes 4 and 6. h e distance to node 4 via node 5 is larger
than the distance already recorded for node 4, which is direct from node 1, so the
entry for node 4 remains the same. h e distance from node 5 to node 6 is 1.944 units.
h is is added to the distance from node 1 to node 5 (1.228), giving a total path length
from node 1 via node 5 to node 6 of 3.172 and the parent node for node 6 is set to 5
(i.e. the connection back to node 1 is via node 5). h is distance replaces the ini nity
value for node 6. h is gives the table 'At er iteration 2.
h e shortest distance for any non-included node is 1.566, for node 4, so this node is
now included. Node 4 is connected to nodes 2, 3, and 6. h e distance from node 1 to
node 2 via node 4 is greater than the direct link between node 1 and node 2, so the entry
for node 2 remains the same. h e distance from node 1 to node 3 via node 4 is 1.566 +
1.495 = 3.061 and this value replaces the ini nity value for node 3, for which the parent
node is set to 4. h e distance from node 1 to node 6 via node 4 is 1.566 + 1.068 = 2.634.
h is is smaller than the existing distance value for node 6, so the distance value is
replaced and the parent node is changed to 4. h e result is the table 'At er iteration 3.
Search WWH ::
Custom Search