Learn Floyd–Warshall Algorithm
We are given a directed or undirected weighted graph with vertices. We need to find the shortest distance between every pair of vertices and .
The graph may contain edges with negative weights, but it must not contain any negative-weight cycle.
This algorithm can also be used to detect negative cycles: if after the algorithm finishes we get
for some vertex , then the graph contains a negative cycle.
The Floyd–Warshall algorithm builds the answer step by step.
At each stage, we decide whether it is useful to pass through one more vertex when going from to .
Before stage , the value d[x][y] stores the length of the shortest path from to whose internal vertices belong only to the set
Here, internal vertices mean all vertices on the path except the start and the end.
For the initial stage, we set:
d[x][y] = w[x][y] if there is an edge from to with weight ;d[x][y] = inf if there is no edge;d[x][x] = 0 for every vertex .Now suppose we are at stage and want to update the matrix.
For every pair of vertices , there are two possibilities:
In the second case, the path can be split into two parts:
Both of these parts use only internal vertices from the set , so their lengths have already been computed.
Therefore, the transition is:
So at each stage, we simply try to improve every pair by passing through vertex .
After all stages, d[x][y] will contain the length of the shortest path from to $y, or inf` if no such path exists.
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}