RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Network Know-How: Finding Shortest Paths : Page 2

Ever wonder how a GPS or mapping program calculates the shortest path between two locations? Learn how to quickly find the shortest paths through street, telephone, airline, and other networks.

Building Networks
Building networks in Visual Basic or C# is easy.

To represent a node, make a node class that includes a list or collection of links. This class should also include a label, X and Y coordinates, colors, and anything else you need to draw the node appropriately.

The following code shows a simple PathNode class. It includes Label, X, and Y drawing properties. It uses a generic list of PathLink objects (described next) to store links that leave this node.

   Imports System.Collections.Generic
   Public Class PathNode
       Public Label As String
       Public X As Single
       Public Y As Single
       Public Links As New List(Of PathLink)
       Public IsInCl As Boolean
       Public BestDist As Single
       Public BestLink As PathLink
   End Class
You can see three other variables in the preceding code that store additional information needed by the shortest-path algorithms described in this article:

  • IsInCl: Whether a node is in a candidate list
  • BestDist: The best distance from a starting node to this node
  • BestLink: The link you would follow to traverse the shortest path
You'll see how these are used shortly.

To represent links, make a link class. At a minimum, this class must have two properties that refer to the link's end nodes. If the network is directed, those properties must let you determine the link's start and end node.

The link class should also define a cost. To draw the link, you may need additional variables for colors, thickness, and other drawing properties.

The following code shows a simple link class for a directed network. The IsInPathTree variable is used by the program to draw the results.

   Public Class PathLink
       Public Cost As Single
       Public FromNode As PathNode
       Public ToNode As PathNode
       Public IsInPathTree As Boolean = False
   End Class
You can also give the node and link classes methods for drawing, locating points (for example, determining whether the node is at a point clicked by the user), and so forth. This article's example programs include several methods for initialization, drawing, and performing other incidental chores—but they're not central for the shortest-path algorithms so they're not described here. Download the examples and take a look for yourself.

Over the years, people have devised many shortest-path algorithms with different levels of speed and complexity. You can divide these algorithms into two broad categories: label-setting and label-correcting algorithms.

The following section describes a popular label-setting algorithm. The section after that explains a label-correcting algorithm that is less well-known, but often faster.

Before you can dig into the meat of these algorithms, however, you need to understand shortest-path trees.

Shortest Path Trees
Finding the shortest path from one node to another in a network actually involves more than finding a single path. When you look at a street map, you may be able to intuitively guess a near-optimal path without looking at all the dead ends, cul-de-sacs, side streets, and other clutter that obviously won't play a part in the final path.

For example, if you look at a highway map of the United States and try to find a route from San Diego to New York, you probably won't bother to look at roads in Florida or Alaska.

Unfortunately, shortest-path algorithms cannot make similar leaps of intuition. There are a couple of good reasons for this. First, in some networks it may be very hard to tell which links are obviously not useful. For example, in a street network, the time to traverse a link is related to its length, but in other networks a link may have practically any cost. Suppose there were a very fast link from Tampa, Florida to New York City (some sort of transporter, perhaps). In that case, the shortest path from San Diego to New York might require you to visit Tampa. In a real street network, that won't work, but it's not so easy to discard unintuitive solutions in networks in general.

Second—and perhaps more important: These algorithms just aren't that smart. You could add code to try to identify parts of the network that obviously won't be part of the final solution but that would complicate the algorithm and might actually slow overall performance. These algorithms contain very tight loops that are executed many, many, MANY times very quickly. Adding special tests to help find the shortest paths makes the algorithm more intelligent, but usually slows the loops down and gives you a net loss. I'll talk about a couple of changes that sometimes pay dividends later, but in general don't clutter the loops unnecessarily.

Figure 2. Plentiful Paths: Shortest-path algorithms find the shortest paths from one node to every other node.
Because these algorithms cannot use intuition to eliminate obviously wrong paths, it's actually easier for them to calculate the shortest path from one node to every other node in the network rather than just finding the shortest path between two nodes.

For example, Figure 2 shows the same directed network shown in Figure 1. Here the program has found all the shortest paths from node A to every other node in the network and has drawn those paths in red. For example, the shortest path from node A to node G is A-C-E-F-G.

Because the links used in these shortest paths form a tree, this is called the shortest-path tree rooted at node A.

After you find a shortest-path tree, finding the shortest path to a particular node is easy. You just start at the destination node and move back up through the tree following each node's parent until you reach the root node.

Figure 3. Great Grid: Depending on the network, there may be many shortest paths between two nodes.
For example, to find the path from node A to node D, you start at node D and move to its parent node E. From there you move to node E's parent, which is node C. You then move to node C's parent, which is node A. That's the root of the shortest-path tree so you're done. Reversing the order of the nodes you visited, the full path is A-C-E-D.

Before moving on to label-setting algorithms, note that the shortest-path tree is not unique. For a given network, there may be many paths from one node to another that all have the same length.

For example, consider the network shown in Figure 3. If every link has the same cost, then every path (that doesn't obviously backtrack) from node A to node T has cost 7. (It's actually kind of interesting to figure out how many minimal paths there are between two nodes in this network, but that's a topic for another article.)

At any rate, remember that a shortest-path algorithm finds a shortest-path tree but not necessarily the only possible one.

With this background, it's time to look at label-setting algorithms.

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date