Created
June 22, 2012 16:26
-
-
Save obstschale/2973834 to your computer and use it in GitHub Desktop.
Floyd-Warshall Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void floyd_warshall(int dist[ ] [SIZE], int P[ ][SIZE], int n) | |
| { // including array P to record paths | |
| int i, j, k; | |
| // initialise P to all -1s | |
| for (k = 0; k < n; ++k) | |
| for (i = 0; i < n; ++i) | |
| for (j = 0; j < n; ++j) | |
| { | |
| // check for path from i to k and k to j | |
| if ((dist[i][k] * dist[k][j] != 0) | |
| && (i != j)) | |
| { | |
| // check shorter path from i to k and k to j | |
| if ((dist[i][k] + dist[k][j] < dist[i][j]) | |
| || (dist[i][j] == 0)) | |
| { | |
| dist[i][j] = dist[i][k] + dist[k][j]; | |
| // extra line P[i][j] = k; | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Warshall’s Algorithm computes the transitive closure of a directed graph.
Floyd-Warshall’s Algorithm computes all-pairs shortest path for a weighted directed graph (Floyd’s extension to Warshall’s Algorithm).
Another matrix, P, where P[i][j] holds the vertex, k, that Floyd-Warshall found
for the smallest value of dist[i][j], i.e. distance from i to j via k.