Previous: Examples Up: Examples Next: Synchronizing Single-Reader Single-Writer Stream

All-Pairs Shortest Paths

This program calculates the length of the shortest path between all pairs of vertices in a directed, acyclic graph. The graph is defined statically by its adjacency matrix.

#include <iostream.h>
const int N = 4;

int min (int a, int b)  
{
  if (a < b)  return a;
    else      return b;
}

sync int path_lengths[N+1][N][N];
int edges[N][N] = { 0,    1,    8,   4,
                    1,    0, 1000,   2,
                    8, 1000,    0,   4,
                    4,    2,    4,   0 };

void initialize_paths (void)  
{
  for (int i=0; i<N; i++)
    for (int j=0; j<N; j++)
      path_lengths[0][i][j] = edges[i][j];
}

void solve (void)
{
  for (int k=1; k<=N; k++)
    parfor (int i=0; i<N; i++)
      parfor (int j=0; j<N; j++)
        path_lengths[k][i][j] = min (path_lengths[k-1][i][j],
                   path_lengths[k-1][i][k-1] + path_lengths[k-1][k-1][j]);
}

void display_result (void)
{
  cout << "All-pairs distance matrix is:" << endl;
  for (int i=0; i<N; i++)  {
    for (int j=0; j<N; j++)  {
      cout << path_lengths[N][i][j] << "\t";
    }
    cout << endl;
  }
}

int main()
{
  initialize_paths();
  solve();
  display_result();

  return 0;
}

This example uses the dynamic programming recurrence relation where is the minimum distance between vertices and , using only vertices numbered strictly less than as intermediate vertices.

In this example, all calculations are composed in parallel with each other. If any of the three values required to calculate path_lengths[k][i][j] are not yet defined, that thread of control suspends. Thus, the order of evaluation of this three-dimensional array is controlled by the data dependencies of each element of the array on the previous elements. Again, it is important to note that the small size of each task to be performed in parallel relative to the number of these tasks makes this program extremely inefficient. The dominant cost here is the thread creation and termination time (as opposed to the calculations performed) and thus we would expect to observe a degradation in performance in any practical implementation. This example is meant only to illustrate the semantic meaning of single-assignment variables and the functional style of programming they induce.