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.