Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Finding My Summer Vacation's Shortest Path

August 21, 2012

Back when gas prices were below a dollar per gallon, my family would take cross-country driving trips. When we were planning how to get from point A to point B, we consulted a paper map, especially if we hadn't been there before. Besides allowing you to trace possible routes, a map usually had a lower triangular matrix with the precomputed distances between a set of cities found on the map (and some that might be just off the edge of the paper). Looking at the intersection of rows/columns for, say, Albuquerque and Boston, I would find that the shortest route known to the cartographers was 2232 miles. Since there isn't one road that connects these two cities, how did those mapmakers compute the shortest distance between these two places? (Remember that Google Maps wasn't even the glimmer in anyone's eye back then.)

Think of a map as an instance of a graph, the cities are the nodes and the roads between cities are the edges. The length of the road is the weight of the corresponding edge. The All-Pairs Shortest Path problem asks you to compute the minimum length path (shortest distance) between all pairs of nodes within the graph. Thus, besides computing the shortest distance needed to drive between Albuquerque to Boston, you can also find the minimum driving distance between Charlotte and Detroit, Ellensburg and Frankfort, or Greenwich and Hilton Head.

The All-Pairs Shortest Path problem takes a graph of n nodes represented by an n x n weight matrix, W. The result is an n x n matrix, D (for distance), where the D[i][j] entry holds the minimum weight of the path from node i to node j. Entries in the W matrix can be zero, positive (if a direct edge lies between the two nodes), or the infinity value (∞) where there is no direct edge between the nodes. The main diagonal of W is filled with zeroes to denote that it takes no time or distance to travel from a node to itself. It is okay to have negative weights in the W matrix as long as there is no negative length cycle. This condition will assure that only simple paths are found. (For a graph that models physical distances, you won't have negative values. However, if the edge weights are for something like tolls on the roads, a negative weight might represent a payment you receive for travelling between the two nodes.)

Floyd's Algorithm is a simple solution to this problem. The key point to the algorithm is to find the shortest path between node i and node j that includes (or excludes) node k on the path. For each pair of nodes, each possible node k in the graph is tried in turn to find these shortest paths. The algorithm computes a series of successive Dk matrices, one for each individual k, with the previous Dk-1 matrix used in the computation. In formal notation, we compute the value of an [i][j] entry from the previous matrix (i.e., look for a shorter path that uses node k) with the following formula:

Dk [i][j] = min(Dk-1 [i][j], Dk-1 [i][k] + Dk-1 [k][j])

After k iterations, the Dk matrix will hold the lengths of the shortest paths that use the first k nodes as intermediate nodes in the path. Once the algorithm has iterated over all n nodes in the graph, the Dn graph will contain the shortest path lengths between all pairs of nodes with some combination of other nodes as intermediate nodes. This is the result that we are looking for.

From the above description, I can see that there will be a nested loop pair to compute the minimum path between each i,j pair. This computation is going to be the body of the loop that iterates over all the choices for k. If the initial D0 matrix is simply the original weight matrix, W, a serial code implementation of Floyd's Algorithm is shown here.

void Floyds(float **D, int N)
{
  int i, j, k;

  for (k = 0; k < N; k++) {
    for (i = 0; i < N; i++) {
      for (j = 0; j < N ; j++)
        D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
    }
  }
}

I've elected to use a float array for both the weight and distance matrices. The constant FLT_MAX from the float.h include file (not shown, but assumed to be part of the initialization of W) is used to play the role of infinity for nodes not directly connected by an edge.

If you're in a hurry to find the distance between your starting point and somewhere exotic that is within your travel time budget, you might want to implement and run a parallel version of Floyd's Algorithm on multiple cores. One point to consider in such a conversion is that the iterations of the outer loop are similar to a time series computation. What I mean is that the algorithm must finish all updates to the D matrix entries for each k before going to the computation using k+1. Thus, the outer loop must be run in serial and the two inner loops are the only possible candidates that can be made to run concurrently.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video