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.

The following PathSLink class represents a link between two nodes.

class PathSLink { public enum LinkUseageType { Unused, InTree, InPath } public PathSNode Node1, Node2; public int Cost; public LinkUseageType LinkUsage = LinkUseageType.Unused; }

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.

// Find a shortest path tree rooted at this node // using a label setting algorithm. private void FindPathTree(PathSNode root) { if (root == null) return; Root = root; List candidates = new List(); // Reset all nodes' Marked and NodeStatus values, // and all links' Used and LinkUsage flags. ResetPathTree(); // Start with the root in the shortest path tree. root.Dist = 0; root.InLink = null; root.NodeStatus = PathSNode.NodeStatusType.NowInList; candidates.Add(root); // Process the candidates. while (candidates.Count > 0) { // Find the candidate closest to the root. int best_dist = int.MaxValue; int best_i = -1; for (int i = 0; i < candidates.Count; i++) { PathSNode candidate_node = candidates[i]; int new_dist = candidate_node.Dist; if (new_dist < best_dist) { best_i = i; best_dist = new_dist; } } // Add this node to the shortest path tree. PathSNode node = candidates[best_i]; candidates.RemoveAt(best_i); node.NodeStatus = PathSNode.NodeStatusType.WasInList; // Examine the node's neighbors. foreach (PathSLink link in node.Links.Values) { PathSNode to_node; if (node == link.Node1) { to_node = link.Node2; } else { to_node = link.Node1; } if (to_node.NodeStatus == PathSNode.NodeStatusType.NotInList) { // The node has not been in the candidate list. // Add it. candidates.Add(to_node); to_node.NodeStatus = PathSNode.NodeStatusType.NowInList; to_node.Dist = best_dist + link.Cost; to_node.InLink = link; } else if (to_node.NodeStatus == PathSNode.NodeStatusType.NowInList) { // The node is in the candidate list. // Update its Dist and inlink values if necessary. int new_dist = best_dist + link.Cost; if (new_dist < to_node.Dist) { to_node.Dist = new_dist; to_node.InLink = link; } } } // foreach (PathSLink link in node.Links) } // while (candidates.Count > 0) GotPathTree = true; // Mark the inlinks so they are easy to draw. foreach (PathSNode node in Nodes.Values) { if (node.InLink != null) { node.InLink.LinkUsage = PathSLink.LinkUseageType.InTree; } } // Start with no destination. Destination = null; // Redraw the network. this.Refresh(); }

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.

Download the example to experiment with it and to see additional details.