Index Books FAQ Contact About Rod

# Title: Find shortest paths in a network C#

This example shows one method for finding shortest paths in a network such as a street, telephone, or computer network. It's a fairly advanced example adapted from my book Essential Algorithms: A Practical Approach to Computer Algorithms. See the book for more in-depth discussion and for a description of lots of other interesting algorithms.

To use the program, open the File menu and select Open to load a network from a text file. Click the left mouse button on a node to build the shortest path tree (described shortly) rooted at that node. Then right-click on a node to display the shortest path from the root node to the node you right-clicked.

The following PathSNode class represents a node in the network.

class PathSNode { public enum NodeStatusType { NotInList, WasInList, NowInList } public int Id; public Point Location; public Dictionary Links = new Dictionary(); public int Dist; // Distance from root. public NodeStatusType NodeStatus; // Path tree status. public PathSLink InLink; // The link into the node. }

Most of this is straightforward. The Links field holds the links that lead in or out of this node. The Dist, NodeStatus, and InLink fields are used by the shortest path algorithm described later.

This class is also fairly straightforward, except perhaps for the LinkUsage field. It's also used by the algorithm described shortly.

The following FindPathTree method uses a label setting method to find a shortest path tree rooted at a particular node. By following links from a destination node back through the tree, you can trace the shortest path from the root node to the destination node.

The basic idea is this. The algorithm builds a shortest path tree incrementally. It keeps a candidate list that holds nodes that are one link away from some node that is in the current shortest path tree. It keeps track of the best distance so far through the tree to every node in the tree and to the nodes in the candidate list.

While the candidate list is not empty, the program finds the node in the list with the shortest distance to the root node. Because that node is the closest one to the root, adding other nodes to the shortest path tree cannot improve the path to this node. (You can think about why this is true, but the idea is that any path to this node via some other node that is not yet in the tree would be longer.) The program adds that node to the shortest path tree and removes it from the candidate list.

Next the program considers all of the neighbors of the newly added node. If the path to a neighbor via this node is shorter than the path it has currently recorded to the root node, then the program updates the neighbor's path to use the newly added node. It then adds the neighbor to the candidate list (if it is not already in the list).

The program continues this process, removing a node from the candidate list, adding it to the shortest path tree, and adding its neighbors to the candidate list until the list is empty. At that point the shortest path tree is complete.

This algorithm is called a "label setting" algorithm because once you add a node to the shortest path tree, it is labeled with it's final distance to the root node and that distance is never changed. (In contrast, a "label correcting" algorithm may add a node to the tree with a given distance and then later update its distance when it finds a better path to the node.)

I know this discussion is fairly terse. See the code for additional details such as how the program loads a network from a text file and how it handles mouse clicks. See my book Essential Algorithms: A Practical Approach to Computer Algorithms for a more complete explanation, more information on shortest path algorithms, and other useful algorithms.