Floyd Warshal Algorithm

#Day 6

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)

fw
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.

fw1
Image: 2

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

path(a->b) >path(a->c->b).

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]

dmsn fk

For Intermediate vertex as 1

we get the following table

fw1
Image: 3

Then for intermediate vertex as 2 we get

fw1
Image: 4

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

fw2
Image: 5

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.

Time Complexity

The time complexity of this algorithm is  O(|V|^{3}).

Source Code

Source code for the implementation of this algorithm can be found here. Source code link

Hackerrank Problem

Hackerrank has a problem which uses this algorithm.

Problem Link

Solution Link

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s