Floyd-Warshall

Teaching‎ > ‎Parallélisme et Distribution‎ > ‎

Floyd-Warshall

All pairs shortest path

The goal of this project is to implement an all-pairs shortest path using the Floyd-Warshall algorithm. The result is the shortest path (number of hops) between any pair of vertices in a graph.

Overview of the project :

  • We consider a positive weighted directed graph. Weights are positive integers.
  • The number of vertices is n=2^k
  • This graph can be represented as a matrix A such that
    • aij = 0 if i = j
    • aij = weight of (i,j) if there is an edge between i and j
    • aij = 0 otherwise
  • The result will be a matrix D of size n x n where dij represents the distance between i and j.

The algorithm works as follows :

  • Take matrix A and transform it into an adjancency matrix W such that
    • wij = 0 if i = j
    • wij = weight of (i,j) if there is an edge between i and j
    • wij = +inf otherwise
  • Compute W^n by replacing the multiplication operation with an addition and the addition with a min.
  • The result is the all-pairs shortest path.

Example :

graph.jpg

Matrix A

0 1 2 0 0 0 0 1 0 3 0 6 0 0 0 0

Matrix W

0 1 2 +inf +inf 0 +inf 1 +inf 3 0 6 +inf +inf +inf 0

W^2 (and later W^4)

0 1 2 2 +inf 0 +inf 1 +inf 3 0 4 +inf +inf +inf 0

Using this matrix, we can see the cost from D toward any other vertex is +inf because there is no path from D. The cost from A to D is 2.

Submission

The individual project is to be submitted through a GitHub private repository (invite fabricehuet) and have the following:

  • A file surname.c containing your code, a file surname.txt with some explanations (what you have implemented, how you did it...).
  • Use MPI for communication and OpenMP for parallel computing.
  • Assume a ring topology.
  • Matrix A will be given as an input file on the command line. It is well formed (one line per matrix line, space-separated weights).
  • The result will be output on the standard output using the same format as input.
  • +inf will simply be output as i
  • Your code should handle the case where thee number of processors is not a divisor of N.