Snakes and Active Contours - Bezier and Splines in Image Processing and Machine Vision - page 190

principle better, let's consider the the shortest path between the cities of Bris-
bane and Sydney. We assume that the shortest path between these cities passes
through the city of, say, Armidale. Immediately we can say that the shortest
path between Brisbane and Armidale is just that section of the Brisbane-
Sydney shortest path that lies between Brisbane and Armidale. Why? Well, if
there existed a path between Brisbane and Armidale that was shorter than the
one already found, then that original path from Brisbane to Sydney via Armi-
dale could not have been the shortest path between those cities—so we have
proof by contradiction. Hence all subpaths of a shortest path must themselves
be shortest paths between their respective endpoints. Reversing the argument,
we see that new shortest paths can be found by recursively extending known
shortest paths.
Fig. 9.7. Shortest path in a graph or network problem.
Dijkstra's Algorithm for the Shortest Path on a Network
The above insight leads directly to Dijkstra's algorithm for the single-source
shortest path problem for a directed graph with nonnegative edge weights.
Let us determine the shortest path from node A to Z, say, in the network of
Figure 9.7. We know initially that the shortest path to A is the null path of
cost 0. From the Principle of Optimality we know our solution can be obtained
by extending known shortest paths, in this case the null path. So we follow
all paths leading out of A to reach the following nodes with their associated
path costs: