Login | Register   
LinkedIn
Google+
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 3

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-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.
  6.  
    Figure 4. Tree Farming: These frames show the growing shortest-path tree.
  7. Remove that node from the candidate list.
  8. 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.



Comment and Contribute

 

 

 

 

 


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

 

 

Sitemap