Graphics Reference
In-Depth Information
(known)
A
0
|
B
1
,C
3 (trial)
.
Here we have partitioned our nodes into
known
, where we now know the short-
est path to the node, and
trial
where we are yet to determine the shortest
path. Now AB of cost 1 must be the shortest path from A to B as any alter-
native path must go via AC, which has cost 3 already. It will always be the
case that the trial node with minimum path cost found so far will be the end
node of a new shortest path. Now we know that the shortest path AZ can be
constructed by extending shortest paths, so now we follow all paths leading
out of B, except those leading back to known nodes, and then add B to the
known nodes list, which yields the following nodes and costs:
(known)
A
0
,B
1
|
C
2
,D
4
.
(trial)
.
In this case, we have found an alternate route to C via B with cost 2, which is
lower than the cost found so far. So we have updated the cost to C with the
new value. We now know that there is no shorter path to C other than the
one we have found since any alternate path would have to go via D, which has
cost 4. This process is repeated until we reach reach node Z. The complete
sequence is given in Table 9.1. All that remains to complete the algorithm
is to maintain a list of backward pointers for each node, which will allow us
to backtrack along the shortest paths to the starting node. The steps of the
algorithm including the backward pointers are shown in Table 9.2 and the
pseudo-code is given in Figure 9.8.
Table 9.1.
Evolution of Dijkstra's algorithm on the network of Figure 9.7. Shortest
path costs to known nodes are shown in bold. The cost of the shortest path from A
to Z is 8.
A B C D E F G Z
0
∞ ∞ ∞ ∞ ∞ ∞ ∞
0
1
∞ ∞ ∞ ∞ ∞
0 1
2 4
∞ ∞ ∞ ∞
0 1 2
4 7 6
∞ ∞
0 1 2 4 5
6 6 11
0 1 2 4 5 6
6 11
0 1 2 4 5 6 6
8
0 1 2 4 5 6 6 8
3
It is useful to visualize the evolution of Dijkstra's algorithm as an expand-
ing wavefront. At each stage of the algorithm, the minimum distance node
is found and paths leading out of this node are followed yielding another
shortest path. Dijkstra's algorithm is closely related to the Fast Marching Al-
gorithm introduced by Sethian [149, 150], which is used in both Level Sets
and Geodesic Active Contours.
Search WWH ::
Custom Search