RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Network Know-How: Finding Shortest Paths

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.

n my Taming Trees series of articles (see the Related Resources for links), I explained how you can store and manipulate hierarchical data. Those articles showed how to build trees, where each node in the tree may have many children.

This series of articles discusses a generalization of trees called networks. In a tree, every node must have exactly one parent node (except for the tree's root node, which has no parent).

In a network, any node (sometimes called a vertex) may be connected by links (also called edges) to any number of other nodes. Depending on the problem, links may be directed (pointing in one direction) or undirected (you can move across a link in either direction) but there's no notion of a parent node and no root.

In most representations, a link also has a cost (sometimes called weight, distance, or length) that gives the cost for traveling across the link. For example, in a street network a link's cost might be the time it takes you to drive across it. In a power network, a link's cost might be the electrical loss when current travels across the link. In a highway network, a link's cost might be the expense of building the corresponding stretch of highway (often more than two million dollars per mile, per lane).

Figure 1. Nifty Network: The blue numbers on this directed network show link costs.
Figure 1 shows a small directed network. The little blue numbers give each link's cost. The letters are just labels so it's easy to refer to the nodes.

Networks can represent many real-world objects, such as the streets in a city, water pipes, power lines, computer networks, storm drains, sewer lines, railroad lines, airline connections, and so forth. In such networks, finding the shortest paths can give you the best route to drive from one point to another, the route through a computer network that uses the fewest resources on intermediate computers, the airline flight with the fewest connections, and so forth.

There are also several more subtle applications that use shortest-path calculations. If you set up a network properly, shortest paths can represent the best sequence of moves to solve problems such as Rubik's Cube or the smallest number of transformations required to convert one piece of text into another (which gives a measure of how similar the pieces are). Shortest-path calculations are also required to perform calculations such as solving the traveling salesperson problem (finding the most efficient order for visiting a series of points and returning to the starting point).

This article explains two methods for finding the shortest paths through a network. Before you can understand those algorithms, however, you need to know how to build a network in Visual Studio.

Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date