Floyd Warshal algorithm is used to find the shortest path between all the edges in a graph. This work with negative weight edges as well. The same algorithm can be used to check if the graph contains a negative weight cycle.
This is algorithm is based on dynamic programming concept. For this algorithm, we make a two-dimensional array of n*n where n is the number of vertices in the graph. We initialize all the fields on diagonal(from top left to right bottom) of the array to 0. Which means every vertex has a path to itself with 0 weight.
For example purpose, we will use following graph (Image: 1)
We fill the rest of the fields as INF(infinite) and replace the fields according to graph with the edges of the graph.
Now to construct the final table, we take all the vertices from 1 to n as c, one by one and check for all the paths from a to b. We check if
If such path exists then we update the field of the table[a][b] with table[a][c]+table[c][b].
def minimum_distance_vertex_pair(graph): n = len(graph) for i in range(n): for j in range(n): for k in range(n): if graph[j][k] > graph[j][i]+graph[i][k]: graph[j][k] = graph[j][i]+graph[i][k]
For Intermediate vertex as 1
we get the following table
Then for intermediate vertex as 2 we get
For vertex 3
If we go to 4 from 1 it is 10 but if we go from 1 to 3 and then 3 to 4 we get 2 +1 which is less than 10 hence we update 10 by 3 and so on and get the following table
For vertex 4
From vertex 4 there exist no path so it does not affect any path. Hence we get the same table as the image: 5 after this iteration.
So finally we get the table as Image: 5
Which says there are few pairs which do not have a path. ex- 2->1, 3->1,3->2 and so on.
Every field in this table says that minimum distance between any a to b is table[a][b]. If it is INF it means there is not path exist for this pair.
Negative Cycle Detection
For the detection of negative cycle, there is one simple rule. If any negative cycle exists in the graph that means from vertex x to x, there is a path with the negative weight. So if we traverse the diagonal of the table after all the iterations and get a negative value that implies there is a negative weight cycle in the graph.
The time complexity of this algorithm is .
Source code for the implementation of this algorithm can be found here. Source code link
Hackerrank has a problem which uses this algorithm.