Databases Reference
In-Depth Information
Figure 7-2. A logical representation of Australia and its arterial road network
Starting at the node representing Sydney in
Figure 7-3
, we know the shortest path to
Sydney is 0 hours, because we're already there. In terms of Dijkstra's algorithm, Sydney
is now
solved
insofar as we know the shortest path from Sydney to Sydney. Accordingly,
we've grayed out the node representing Sydney, added the path length (0), and thickened
the node's border—a convention that we'll maintain throughout the remainder of this
example.
Moving one level out from Sydney, our candidate cities are Brisbane, which lies to the
north by 9 hours, Canberra, Australia's capital city, which lies 4 hours to the west, and
Melbourne, which is 12 hours to the south.
The shortest path we can find is Sydney to Canberra, at 4 hours, and so we consider
Canberra to be solved, as shown in
Figure 7-4
.
