Parallel program (MPI) that uses Repeated Squaring combined with Fox's algorithm to solve instances of the All-Pairs Shortest Path problem.
$ cd src/ && make$ mpirun -np x --hostfile y fox
- replace x and y accordingly
Input consist in an integer N representing the number of nodes in the graph, followed by NxN doubles each representing links, and costs, between pairs of nodes of in the graph. E.g:
6
0 2 0 5 0 0
0 0 0 0 0 0
0 2 0 0 0 5
0 0 0 0 1 0
3 9 3 0 0 0
0 0 0 0 1 0
The corresponding output should be:
0 2 9 5 6 14
0 0 0 0 0 0
9 2 0 14 6 5
4 6 4 0 1 9
3 5 3 8 0 8
4 6 4 9 1 0
Run $ make clean to, optionally, remove the executable.
$ cd test/ && make$ ./exec
- exec is either
fox,memorutil
Tests doesn't cover the totality of the program, I made them as a first introduction to C++ testing.