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 :

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.