235
How Are Shortest Paths Found?
streets that will be traversed on that path. See Figure 8.7 for an example of
using an online geospatial technology utility to compute the shortest path or
best route between two locations. Also check out Hands-on Application 8.4:
Online Mapping and Routing Applications and Shortest Paths on page 236 for
some other Web tools for online directions and routing.
Of course, sometimes you have more than one destination to visit—say
you have three places you want to stop at (shoe store, music store, and book
store) and you want to drive the overall shortest route to hit all three places.
When using geospatial technology to compute a shortest route between several of these stops, there are two types of scenarios to choose from:
1. Finding the shortest path when visiting stops in a pre-defined order: This
means you have to stop at the shoe store first, the music store second,
and the book store last. In this case, you’d want to find the shortest path
FIGURE 8.7 The
“shortest path” (the blue
line) computed from
MapQuest from the White
House to Georgetown
University in Washington,
D.C. (Source: Map(s) and
data © 2011 by MapQuest,
Inc., Navteq, and Intermap
as applicable. MapQuest
and the MapQuest logo are
trademarks of MapQuest, Inc.
Used with permission.)
The inner workings of Dijkstra’s Algorithm are beyond the scope of this book, but there’s an excellent
free online resource that allows you to construct
a sample network, then run the Dijkstra Algorithm
to find the shortest path. The algorithm will walk
through the shortest path step-by-step and describe the actions it’s taking (and how the shortest paths are created). Open your Web browser
and go to http://www.dgp.toronto.edu/people/
JamesStewart/270/9798s/Laffra/DijkstraApplet.
html. On this Website, you can set up a series of
nodes (junctions) and links (edges), assign weights
(transit costs) and directions to them, and run
the algorithm to find the shortest path between the
origin and all destinations on the network. Use the
interactive interface to construct a sample network
(or use the pre-made example) and use Dijkstra to
set up the shortest paths for you.
Hands-on Application 8.3
Solve Your Network Problems with Dijkstra
stops destinations to
visit on a network.
How Are Shortest Paths Found?
streets that will be traversed on that path. See Figure 8.7 for an example of
using an online geospatial technology utility to compute the shortest path or
best route between two locations. Also check out Hands-on Application 8.4:
Online Mapping and Routing Applications and Shortest Paths on page 236 for
some other Web tools for online directions and routing.
Of course, sometimes you have more than one destination to visit—say
you have three places you want to stop at (shoe store, music store, and book
store) and you want to drive the overall shortest route to hit all three places.
When using geospatial technology to compute a shortest route between several of these stops, there are two types of scenarios to choose from:
1. Finding the shortest path when visiting stops in a pre-defined order: This
means you have to stop at the shoe store first, the music store second,
and the book store last. In this case, you’d want to find the shortest path
FIGURE 8.7 The
“shortest path” (the blue
line) computed from
MapQuest from the White
House to Georgetown
University in Washington,
D.C. (Source: Map(s) and
data © 2011 by MapQuest,
Inc., Navteq, and Intermap
as applicable. MapQuest
and the MapQuest logo are
trademarks of MapQuest, Inc.
Used with permission.)
The inner workings of Dijkstra’s Algorithm are beyond the scope of this book, but there’s an excellent
free online resource that allows you to construct
a sample network, then run the Dijkstra Algorithm
to find the shortest path. The algorithm will walk
through the shortest path step-by-step and describe the actions it’s taking (and how the shortest paths are created). Open your Web browser
and go to http://www.dgp.toronto.edu/people/
JamesStewart/270/9798s/Laffra/DijkstraApplet.
html. On this Website, you can set up a series of
nodes (junctions) and links (edges), assign weights
(transit costs) and directions to them, and run
the algorithm to find the shortest path between the
origin and all destinations on the network. Use the
interactive interface to construct a sample network
(or use the pre-made example) and use Dijkstra to
set up the shortest paths for you.
Hands-on Application 8.3
Solve Your Network Problems with Dijkstra
stops destinations to
visit on a network.