Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Network Know-How: Finding Shortest Paths : Page 4

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.


advertisement
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.



Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap