Geography Reference
In-Depth Information
N1
N2
N3
1.129
N4
N5
N6
Figure 6.2
Network used for illustrating the shortest path algorithm, with the length of each
arc indicated. 'N' indicates node.
table' in Table 6.3, each node has a distance from the source node that is ini nity (•)
and the next node back from each node (parent) to the origin is blank. 'Included' indi-
cates nodes which have comprised part of the shortest route to a node at any stage.
Note that, using this approach, costs (e.g. distances) must be positive. h e example is
presented numerically, rather than graphically, as a key concern is to show exactly how
the algorithm operates.
h e description of the shortest path algorithm that follows is based on that given by
Wise (2002) and makes reference to the format shown in Table 6.3:
•
Select the non-included node with the shortest distance to the source.
•
Include this node (i.e. replace 'N' in the i nal column with 'Y'). h e distance
from this node back to the source node is indicated by dist(
n
).
Identify the nodes connected to node
•
n
that are still not included (they have an
entry 'N' in their i nal column). h e distance between each of these nodes (
m
)
and the node
n
is given by d(
nm
).
For each of the
•
m
nodes:
if dist(
n
) + d(
nm
) < dist(
m
) then dist(
m
) = dist(
n
) + d(
nm
) and parent(
m
) =
n
that is, if there is a shorter route from the source node to node
m
via node
n
then the entry for node
m
is updated with the new total distance i gure and the
parent value for node
m
is set to
n
(the previous node along the path from the
origin node). h e algorithm is illustrated below with reference to the
sub-tables that comprise Table 6.3.
Search WWH ::
Custom Search