**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:

- Set all nodes' BestDist values to infinity.
- Set the start node's BestDist value to 0. (Because it is distance zero away from the start node—itself.)
- Add the start node to the candidate list.
- As long as the candidate list isn't empty:
- Find the node in the candidate list with smallest BestDist value.
| |

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

- Remove that node from the candidate list.
- 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.