- The input matrix is overwritten by the matrix of lengths of shortest paths.
- Edge lengths should be nonnegative.
- If there is no edge between two vertices, the length is the constant INFINITY. So input edge length should be substantially less than this constant.
- The cost of travelling from a vertex to itself is 0. So the adjacency matrix has zeroes on the main diagonal.
- No error checking is done on the input.
- The adjacency matrix is stored as a 1-dimensional array and subscripts are computed using the formula: the entry in the ith row and jth column is mat[i*n + j]
- Use the compile flag -DSHOW_INT_MATS to print the matrix after its been updated with each intermediate city.
- Block partition used to divide up the matrix.
djokicx / floyd Goto Github PK
View Code? Open in Web Editor NEWParallel implementation of Floyd's algorithm for solving the all-pairs shortest path problem.