n my Taming Trees series of articles (see the Related Resources for links), I explained how you can store and manipulate hierarchical data. Those articles showed how to build trees, where each node in the tree may have many children.

This series of articles discusses a generalization of trees called networks. In a tree, every node must have exactly one parent node (except for the tree’s root node, which has no parent).

In a network, any node (sometimes called a vertex) may be connected by links (also called edges) to any number of other nodes. Depending on the problem, links may be directed (pointing in one direction) or undirected (you can move across a link in either direction) but there’s no notion of a parent node and no root.

In most representations, a link also has a cost (sometimes called weight, distance, or length) that gives the cost for traveling across the link. For example, in a street network a link’s cost might be the time it takes you to drive across it. In a power network, a link’s cost might be the electrical loss when current travels across the link. In a highway network, a link’s cost might be the expense of building the corresponding stretch of highway (often more than two million dollars per mile, per lane).

	?
Figure 1. Nifty Network: The blue numbers on this directed network show link costs.

Figure 1 shows a small directed network. The little blue numbers give each link’s cost. The letters are just labels so it’s easy to refer to the nodes.

Networks can represent many real-world objects, such as the streets in a city, water pipes, power lines, computer networks, storm drains, sewer lines, railroad lines, airline connections, and so forth. In such networks, finding the shortest paths can give you the best route to drive from one point to another, the route through a computer network that uses the fewest resources on intermediate computers, the airline flight with the fewest connections, and so forth.

There are also several more subtle applications that use shortest-path calculations. If you set up a network properly, shortest paths can represent the best sequence of moves to solve problems such as Rubik’s Cube or the smallest number of transformations required to convert one piece of text into another (which gives a measure of how similar the pieces are). Shortest-path calculations are also required to perform calculations such as solving the traveling salesperson problem (finding the most efficient order for visiting a series of points and returning to the starting point).

This article explains two methods for finding the shortest paths through a network. Before you can understand those algorithms, however, you need to know how to build a network in Visual Studio.

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.

Explore the Label-Setting Algorithm
In a label-setting algorithm, the program examines the network’s nodes and adds them to the shortest-path tree one at a time. When the algorithm adds a node to the tree, the shortest path from the root node to that node is known?and it never changes after that.

You can understand why these algorithms are called “label-setting” if you think of labeling a node with its distance from the root. After this algorithm labels a node with its distance, that distance never changes, so it is set. In contrast, as you’ll see, a label-correcting algorithm labels nodes with distances that may be wrong, and then it must later correct them.

The best-known label-setting algorithm is called Dijkstra’s algorithm. The idea is to keep a “candidate list” that holds all the nodes that are one link away from the current shortest-path tree. At each step, the program finds the node in the candidate list that is closest to the start node and adds it to the shortest-path tree. The program then updates the shortest distances to that node’s neighbors and places them on the candidate list if they are not already on it.

Here’s the algorithm in pseudo code:

1. Set all nodes’ BestDist values to infinity.
2. Set the start node’s BestDist value to 0. (Because it is distance zero away from the start node?itself.)
3. Add the start node to the candidate list.
4. As long as the candidate list isn’t empty:
5. Find the node in the candidate list with smallest BestDist value.

	?
Figure 4. Tree Farming: These frames show the growing shortest-path tree.

6. Remove that node from the candidate list.
7. Examine the node’s links. If you can update a neighbor’s BestDist value, do so, and add the neighbor to the candidate list (if it isn’t already there).

Figure 4 shows this process round-by-round for the network shown in Figures 1 and 2. Working through the process takes a little time but makes the algorithm much easier to understand.

During round 1, the program adds the start node A to the candidate list and sets its BestDist value to 0. It then removes that node from the candidate list so it is now permanently part of the shortest-path tree. Making a specific link to a node part of the shortest-path tree simply involves setting the link’s IsInPathTree variable. Next, the program considers the node’s neighbors B and C.

Node B’s current BestDist value is infinite. Because it is attached to node A with a link of cost 10, and because node A’s BestDist value is 0, you can form a new path to node B via node A with total cost 0 + 10 = 10. That’s less than B’s current BestDist value so you update the BestDist value to 10 and add node B to the candidate list.

Similarly you can update node C’s BestDist value from infinity to 0 + 10 = 10. You then add node C to the candidate list.

That ends round 1. The shortest-path tree isn’t very interesting yet (it only contains node A) so it’s not shown in Figure 4.

In round 2, the program searches the candidate list for the node with the smallest BestDist value. Currently node B has BestDist = 10 and node C has BestDist = 9, so the program selects node C. It removes node C from the candidate list (making it a permanent member of the shortest-path tree) and considers its neighbor node E.

Node E’s BestDist value is infinity. The new path via node C has total cost equal to node C’s BestDist = 9 plus the cost of the link from node C to node E (4) for a total of 13. That’s less than infinity, so the program updates node E’s BestDist value to 13 and adds node E to the candidate list.

In round 3, the program searches the candidate list for the node with the smallest BestDist value. The list contains node B and node E. Currently node B has BestDist = 10 and node E has BestDist = 13 so the program selects node B. It removes node B from the list and considers its neighbors D and E.

Node D currently has BestDist = infinity, so the new path via node B, with cost 10 + 11 = 21, is an improvement. The program sets D’s BestDist value to 21, and adds node D to the candidate list.

The path to node E via node B has cost 10 + 12 = 22. That’s not less than node E’s current BestDist value of 13 so the program doesn’t update it.

In round 4, the program searches the candidate list for the node with the smallest BestDist value. Currently node E has BestDist = 13 and node D has BestDist = 21 so the program selects node E. It removes node E from the list and considers its neighbors, D and F.

Node F currently has BestDist = infinity so the new path via node E, with cost 13 + 14 = 27, is an improvement. The program sets F’s BestDist value to 27 and adds node F to the candidate list.

The path to node D via node E has cost 13 + 5 = 18. That’s less than node D’s current BestDist value of 21 so the program updates it. Node D is already in the candidate list so the program doesn’t add it again.

In round 5, the program searches the candidate list for the node with the smallest BestDist value. Currently node D has BestDist = 18 and node F has BestDist = 27, so the program selects node D. It removes node D from the list and considers its neighbors. Node D has no neighbors (no links point away from it) so that’s the end of round 5.

In round 6, the program searches the candidate list for the node with the smallest BestDist value. Currently the list contains only node F with BestDist = 27. The algorithm removes node F from the list and considers its neighbor G.

Node G currently has BestDist = infinity so the new path via node F, with cost 27 + 13 = 40, is an improvement. The program sets G’s BestDist value to 40 and adds node G to the candidate list.

In round 7, the program searches the candidate list for the node with the smallest BestDist value. Currently the list contains only node G so the program selects node G and removes node E from the list. It then considers node G’s neighbor D.

Node D currently has BestDist = 18. The new path via node G would have total cost 40 + 15, which is not less than 18 so the program does not update node D’s BestDist value. That’s good, because node D is supposedly already part of the shortest-path tree, so you don’t want to update its BestDist value again.

	?
Figure 5. Great Grid: Program LabelSettingBig builds a grid network with added express links to simulate city streets.

At this point the candidate list is empty, so the algorithm is finished.

The program LabelSetting (downloadable in both Visual Basic and C# versions) demonstrates this algorithm. Left-click on a node to select it as the start node and build the shortest-path tree. Right-click on a node to select the destination node. The program will show you the shortest path to that node through the tree.

Figure 5 shows example program LabelSettingBig (also in the download), which is similar to the LabelSetting program, except that it builds a much bigger test network. This network is an undirected grid (there are links pointing both directions between adjacent nodes) with some added express links thrown in. Each express link connects two randomly selected nodes with a cost that is a bit less than the distance between the two nodes. This type of network models most cities’ streets fairly well (except for cities such as Boston and London, where a pile of spaghetti is more accurate).

	?
Figure 6. Gargantuan Grids: The sample program LabelSettingHuge lets you test enormous grid networks.

In Figure 5, I left-clicked the upper left node to make it the start node and right-clicked the lower right node to make it the destination node. The shortest-path tree is shown in red and the shortest path between the two nodes is shown in blue. The total distance between the two nodes is shown in the form’s title bar as 508.13.

The sample LabelSettingHuge program lets you test much bigger networks. It doesn’t draw the networks because a million-link network looks like a big blob. Like program LabelSettingBig, this program builds a grid network with extra express links.

Figure 6 shows program LabelSettingHuge in action. For Figure 6, the network has 250,000 nodes and just fewer than 1,000,000 links. The program built the shortest-path tree using a randomly selected node as the root in a bit over 5 seconds. That’s not too shabby for such a huge network!

For smaller networks, you can set the number of trials to a bigger number to get a sense of the algorithm’s average performance. Usually the time to build the shortest path tree is pretty consistent no matter which node you use as the root node.

Explore the Label-Correcting Algorithm
The label-setting algorithm described in the previous section grows its shortest-path tree by adding the next closest node to the root node. You can visualize the tree as growing from its top level, adding new branches from its leaves and spreading outward from the root through the network.

For a larger network, you can think of the tree as flowing across the network in a wave. Figure 7 shows a label-setting algorithm after 200 rounds of adding nodes to the shortest-path tree. At this point, the tree is mostly flowing across the upper left corner of the network, with a few outlying clusters that followed express links.

	?
Figure 7. Flowing Forest: A label-setting algorithm’s shortest-path tree flows across the network.

The most time-consuming step in a label-setting algorithm is picking the next node to add to the tree from the candidate list. In each round, the candidate nodes are those that are one link away from the nodes that are already in the tree. In Figure 7, they are the nodes that are one link away from a red link. Those nodes form the wave front along the boundary between the red and black links.

If you study the figure for a while, you’ll see that this includes a lot of nodes, so looking through the candidate list can take a while. When you multiply that effort by the number of rounds needed to add every node to the shortest-path tree, it adds up.

A radically different approach is to add just the first node you find in the candidate list. With this method, you spend very little time searching for the next node to add to the tree. The catch, of course, is that you may not always pick the best node to add?so the link you select may not belong in the finished shortest-path tree. When that happens, you must later remove that link and replace it with a better one.

That’s the idea behind label-correcting shortest-path algorithms. The program keeps a candidate list as before, but in each round, the program removes the first candidate it finds and adds it to the tree. If that candidate was initially added to the tree with the wrong link, the algorithm will eventually discover that fact and fix it.

Of course, by the time the algorithm discovers its mistake, the incorrect link may have been used to attach other nodes to the tree, so their paths will be wrong, too. Therefore, instead of the stately wave-like progression of the tree through the network typical of a label-setting algorithm, a label-correcting algorithm adds nodes to the tree very quickly but must fix up a lot of mistakes later.

Here’s the algorithm in pseudo code:

1. Set all nodes’ BestDist values to infinity.
2. Set the start node’s BestDist value to 0. (Because it is distance zero away from the start node?itself.)
3. Add the start node to the candidate list.
4. As long as the candidate list isn’t empty:
5. Pick any node from the candidate list.
6. Remove that node from the candidate list.
7. Examine the node’s links. If you can update a neighbor’s BestDist value, do so, and add the neighbor to the candidate list (if it isn’t already in the list).

If you compare this algorithm to the previous one, there is only one tiny difference. In Step 4a, this algorithm picks any node from the candidate list rather than the one closest to the tree’s root.

	?
Figure 8. Careful Corrections: A label-correcting algorithm sometimes makes mistakes but later corrects them.

Figure 8 shows a sequence of steps performed by this algorithm to find a shortest-path tree in the network shown in Figure 1, Figure 2, and Figure 4.

The rounds shown in Figure 8 are slightly different from those shown in Figure 4 for the label-setting algorithm. In Figure 4, the rounds show when a node was removed from the candidate list, making it a permanent part of the shortest-path tree. In Figure 8, they show when a node’s BestDist value was updated, making it part of the shortest-path tree, but possibly not with its final BestDist value.

When the algorithm starts, it adds the root node A to the candidate list. That step isn’t shown in Figure 8 because it’s boring.

Next, the algorithm removes node A from the candidate list and considers its links leading to nodes B and C.

Node B’s current BestDist value is infinite so the new path via node A is an improvement. The program sets B’s BestDist value to 10 and adds node B to the candidate list (see Round 2 in Figure 8).

Node C’s current BestDist value is also infinite so the algorithm updates its value to 9 and adds it to the candidate list (see Round 3 in Figure 8).

Now the algorithm is done with node A’s neighbors so it takes the next node from the candidate list. It removes node B from the list and considers its neighbors D and E.

Node D’s BestDist value is infinite, so the program updates it to use the new path via node B with a cost of 10 + 11 = 21, and adds node D to the candidate list (see Round 4 in Figure 8).

Node E’s BestDist value is also infinite, so the program updates it to use the new path via node B with a cost of 10 + 12 = 22, and adds node E to the candidate list (see Round 5 in Figure 8).

The program is now done with node B’s neighbors, so it takes the next node (node C) from the candidate list and considers its neighbor node E. Node E’s BestDist value is currently 22 but the new path via node C costs only 9 + 4 = 13, which is less than 22. So the program updates node E’s BestDist value to 13 and records the fact that it should now use the path via node C. Node E is already in the candidate list, so it doesn’t need to add it again. Round 6 in Figure 8 shows this situation. Notice how the program has corrected the link to node E.

The program is now done with node C’s neighbors, so it takes the next node from the candidate list. It removes node D from the list. Node D has no neighbors so it’s done with that node.

The program now takes the next node from the candidate list. It removes node E from the list and considers its neighbors D and F. Node D’s BestDist value is currently 21 but the new path via node E has cost only 13 + 5 = 18, so the program updates node D’s BestDist value to 18 and records the fact that it should now use the path via node E. Node D is no longer in the candidate list so the program adds it to the list (again). Round 7 in Figure 8 shows what happens. The program has again corrected a link?this time the one connecting node D to the shortest-path tree.

If you walk through the rest of the algorithm, you’ll find that the program adds node F via the E-F link.

It then removes node D from the candidate list. Node D has no neighbors so that’s easy.

The program then removes node F from the list and considers its neighbor node G, updating its BestDist value and adding it to the candidate list.

The program then removes node G from the list and considers its neighbor node D. This time it cannot update node D’s BestDist value so it does not add node D to the candidate list.

At this point, the candidate list is empty so the algorithm ends. The resulting shortest-path tree in this case is the same as the one found by the label-setting algorithm, but remember that shortest-path trees are not guaranteed to be unique.

The three sample programs LabelCorrecting, LabelCorrectingBig, and LabelCorrectingHuge (all available in the downloadable code) are similar to the label-setting algorithm programs, but use the label-correcting algorithm instead. It’s interesting to compare the two algorithms’ performance.

Performance Comparisons
In my tests, LabelCorrectingHuge was faster than LabelSettingHuge for smaller networks and slower for really big networks. Table 1 shows some of the times in seconds needed by each program to build shortest-path trees.

For the smaller networks, the label-setting algorithm spends too much time trying to pick the best possible node to add to the tree in each round. In contrast, the label-correcting algorithm spends very little time making that decision, and needs to fix up only a few mistakes so it’s faster overall.

For the bigger networks, the express links play a crucial role. In those networks, the express links (which are built randomly) are much longer and a bit faster than the normal grid links. You can think of them as highway links cutting across a city’s surface streets. Usually it’s faster to use an express link if it starts and ends close to where you need to go. In these networks, the program can follow many incorrect paths before it discovers that the express links can give big improvements for those nodes.

Table 2 shows the results of tests with no express links. This time the label-correcting algorithm does much better because it can’t make such large mistakes before catching them.

Removing the express links makes both algorithms a lot faster, but it makes the label-correcting algorithm really fly! The performance you will get for any given problem will depend on your exact network topology.

Making Improvements
I suspect if you really pick these programs apart, you’ll find that they spend a lot of time inside various Visual Studio classes, such as the generic List(Of PathNode) that they use to store their candidate lists. Adding and removing items from these lists takes a fair amount time.

A List(Of PathNode) also doesn’t provide any help for finding the object that currently has the smallest BestDist value, which would really help the label-setting algorithm. It would be nice to use the SortedList class to locate the best node but the BestDist values of the items in the list change while they are in the list and the SortedList class won’t update itself automatically when that happens.

You can probably achieve better performance if you build your own data structures. A good priority queue would make it a lot easier to find the candidate with the smallest BestDist value and would be fairly easy to update when BestDist values changed. Building priority queues is a topic I’ll save for another day.

Even without building your own data structures, there are a few tweaks you can make to these algorithms that may boost performance. For example, suppose you’re using a label-correcting algorithm and you’re considering the neighbors of a node that you just removed from the candidate list. Suppose further that a neighbor’s best distance can be improved by using the new path via the node you just removed. In that case, there are three possibilities.

First, if the neighbor has never been in the candidate list before, you simply add it.

Second, suppose the neighbor has been in the candidate list before but is not now in the list. In that case, you have previously removed the node from the candidate list and considered its neighbors. But when you did so, you had the wrong value for this node’s shortest distance from the root node. In other words, you made a mistake.

That’s no big deal unless you used that incorrect distance while building other paths! Perhaps some neighbor of this node should have used the new shortcut but didn’t because you had the wrong BestDist value. In that case, you might have made several possibly long paths that must now be corrected.

The improvement is to add this neighbor (which was on the candidate list before but is not now) at the beginning of the candidate list instead of at the end. The idea is that this lets the algorithm reconsider this node and its neighbors sooner, so it can fix existing mistakes before they have a chance to grow even worse.

The third case for a neighbor that should be updated is that it is currently in the candidate list. In this case, you could leave the node alone, or you could try bumping its priority up and moving it to the front of the list.

Another improvement you can sometimes make is to partition the network. For example, the street map for a large country typically contains crowded urban centers separated by large relatively empty areas crossed by major highways. To find the shortest path from one city to another, you can usually find the shortest-path trees for the start and destination cities and then find the shortest path between them through the highway network. This lets you ignore the smaller streets in the other cities.

One final improvement is that, if you initially know the destination node, you can sometimes stop before you finish building the whole shortest-path network. In a label-setting algorithm, for example, you’re done as soon as you reach the destination node. Of course, checking whether you have reached the destination node every time you add a node to the tree takes some time, so the check will improve overall performance only if the start and destination nodes are relatively close together, so you get to stop fairly early.

In a label-correcting algorithm, you can keep track of the best distance to the destination node found so far (initially it will be infinite). After you find a non-infinite path to that node, you can compare other nodes’ distances to this best distance. If a node has a greater best distance, then you don’t need to consider further paths that travel through that node; you might consider the node again later if you find a better path to it but you can skip it for now. This sometimes lets you trim out large swaths of the tree. But again, the tests themselves take extra time, so they’ll only give you a net benefit some of the time. Often it’s better to just grit your teeth and build the whole shortest-path tree.

Shortest-path calculations have many obvious uses, such as finding routes through street networks, but they also have subtler uses, such as helping you determine how similar two pieces of text are.

Using the label-setting and label-correcting algorithms described in this article, you can find shortest paths through even huge networks. In one test (with no express links), a label-correcting program found a shortest-path tree through a network containing one million nodes and almost four million links in about one second. However, when I tried a network with ten million nodes, I ran out of memory. But for now, a million-node network is probably big enough for my day-to-day needs.