234
Chapter 8 Getting There Quicker with Geospatial Technology
direct routes and eliminate some of the longer or more circuitous routes.
However, a shortest path can mean different things. For instance, driving
through city streets may be the shortest physical driving distance (in terms
of mileage), but if those streets have lots of stop lights and traffic congestion,
then this “shortest path” will likely take longer in terms of the time spent driving, rather than traveling a longer distance on a highway that does not have
these impediments. In this case, if you wanted to minimize the time spent driving, the highway route would likely get you to work faster, but you’d actually
be driving a longer distance. Major city streets may take a long time to traverse
at rush hour, but you might sail through quickly if you’re driving on them late
at night.
All of these are things to consider when figuring out the shortest path (or
“best route”) to take when traveling from an origin to a destination. People
use their own decision-making criteria when determining the shortest path
they’re going to take—things like “always use main roads” or “try to use highways whenever possible” or “don’t make a left turn.” For this reason, vehicle
navigation systems often offer multiple options, such as “shortest distance”
or “shortest driving time” or “avoid highways” to compute the best route between points.
Within a vehicle-navigation system (or GIS), each line segment has a
transit cost (or impedance) assigned to it. The transit cost reflects how many
units (of things like distance or travel time) it takes to traverse that edge. For
example, the transit cost may reflect the actual distance in miles from one
junction to another along the edge. The transit cost could also be the equivalent driving time it takes to traverse that particular segment. Whatever transit cost is used, that value will be utilized in the shortest path computation.
Other impedance attributes can be modeled as well—segments could have a
different transit cost under certain conditions (such as heavy traffic or construction). These types of impedance factors can help in making a network
more realistic for use.
The shortest path is then calculated using an algorithm, or a set of steps
used in determining the overall lowest transit cost to move along the network
from a starting point to a destination. There are various types of shortest path
algorithms, including Dijkstra’s Algorithm (see Hands-on Application 8.3:
Solve Your Network Problems with Dijkstra for more information on how to use
this algorithm), which will compute the path of lowest cost to travel from a
starting point to each destination in the network. For instance, say you have
three different destinations you plan to travel to (work, the pizza shop, and
the grocery store). Dijkstra’s Algorithm will evaluate the overall cost from
your home to each destination and find the shortest path from your home to
work, from your home to the pizza shop, and from your home to the grocery
store.
Whatever type of algorithm is used, the system will compute the shortest
path, given the constraints of the network (such as transit cost or directionality of things like one-way streets). The system can then generate directions
for you by translating the selected path into the various turns and names of
transit cost a value
that represents how
many units (of time
or distance) are used
in moving across a
network edge.
algorithm a set of
steps used in a process
(for example, the steps
used in computing a
shortest path).
Dijkstra’s Algorithm
an algorithm used in
calculating the shortest
path between an
origin node and other
destination nodes in a
network.
shortest path the
route that corresponds
to the lowest
cumulative transit cost
between stops in a
network.
Chapter 8 Getting There Quicker with Geospatial Technology
direct routes and eliminate some of the longer or more circuitous routes.
However, a shortest path can mean different things. For instance, driving
through city streets may be the shortest physical driving distance (in terms
of mileage), but if those streets have lots of stop lights and traffic congestion,
then this “shortest path” will likely take longer in terms of the time spent driving, rather than traveling a longer distance on a highway that does not have
these impediments. In this case, if you wanted to minimize the time spent driving, the highway route would likely get you to work faster, but you’d actually
be driving a longer distance. Major city streets may take a long time to traverse
at rush hour, but you might sail through quickly if you’re driving on them late
at night.
All of these are things to consider when figuring out the shortest path (or
“best route”) to take when traveling from an origin to a destination. People
use their own decision-making criteria when determining the shortest path
they’re going to take—things like “always use main roads” or “try to use highways whenever possible” or “don’t make a left turn.” For this reason, vehicle
navigation systems often offer multiple options, such as “shortest distance”
or “shortest driving time” or “avoid highways” to compute the best route between points.
Within a vehicle-navigation system (or GIS), each line segment has a
transit cost (or impedance) assigned to it. The transit cost reflects how many
units (of things like distance or travel time) it takes to traverse that edge. For
example, the transit cost may reflect the actual distance in miles from one
junction to another along the edge. The transit cost could also be the equivalent driving time it takes to traverse that particular segment. Whatever transit cost is used, that value will be utilized in the shortest path computation.
Other impedance attributes can be modeled as well—segments could have a
different transit cost under certain conditions (such as heavy traffic or construction). These types of impedance factors can help in making a network
more realistic for use.
The shortest path is then calculated using an algorithm, or a set of steps
used in determining the overall lowest transit cost to move along the network
from a starting point to a destination. There are various types of shortest path
algorithms, including Dijkstra’s Algorithm (see Hands-on Application 8.3:
Solve Your Network Problems with Dijkstra for more information on how to use
this algorithm), which will compute the path of lowest cost to travel from a
starting point to each destination in the network. For instance, say you have
three different destinations you plan to travel to (work, the pizza shop, and
the grocery store). Dijkstra’s Algorithm will evaluate the overall cost from
your home to each destination and find the shortest path from your home to
work, from your home to the pizza shop, and from your home to the grocery
store.
Whatever type of algorithm is used, the system will compute the shortest
path, given the constraints of the network (such as transit cost or directionality of things like one-way streets). The system can then generate directions
for you by translating the selected path into the various turns and names of
transit cost a value
that represents how
many units (of time
or distance) are used
in moving across a
network edge.
algorithm a set of
steps used in a process
(for example, the steps
used in computing a
shortest path).
Dijkstra’s Algorithm
an algorithm used in
calculating the shortest
path between an
origin node and other
destination nodes in a
network.
shortest path the
route that corresponds
to the lowest
cumulative transit cost
between stops in a
network.