About Floyd warshall algo

#1

what is the basic intuition of this algo and also how to detect the negative cycle. it is not mentioned in video

#2

hello @Senjuti256

Let us assume a graph with V nodes, and let dist[a][b] initially represent the cost of edge from a to b (i.e. the cost of path from a to b without any intermediate node).

for (k = 0; k < V; k++) 
{ 
    for (i = 0; i < V; i++) 
    { 
        for (j = 0; j < V; j++) 
        { 
            if (dist[i][k] + dist[k][j] < dist[i][j]) 
                dist[i][j] = dist[i][k] + dist[k][j]; 
        } 
    } 
}

After the first pass (i.e. when we are done for k==0), dist[a][b] will tell us the shortest path-cost from a to b, but now, it will also include any paths that have only 1st node as an intermediate. Here, we are just checking, if the first node is an intermediate between two edges.
Example:
Assume that from a gives dist matrix we have
4->2->1->3
If we have an edge from 4 to 2, another from 2 to 1, and another from 1 to 3, in the first pass we are just checking if 1 is an intermediate between any two edges. And as it is, we can now say, 2 is connected to 3.
After second pass, dist[a][b] will tell us the shortest path-cost from a to b, but now, it will also include any paths that have only 1st node, 2nd node or both as an intermediate.
Example:
From given dist matrix we have
4->2->1->3
After first pass we have,
4->2----->3
(taking the path from 2 to 3 via 1 as another edge)
Now, considering 2nd node as an intermediate, we can see, we can connect 4 to 3.
Now tough this path seems to have only 2 as an intermediate, but path from 2 to 3 already has 1 as an intermediate, so the new paths may have one or both of them as intermediates.
Similarly, after first k passes, dist[a][b] will tell the length of the shortest path-cost from a to b that uses only the first k vertices as intermediates in the path.
At last we will get all the shortest path-costs that may have first V nodes as an intermediate.

to detect cycle .

step1 ) run floydwarshall algorithm and prepare the distance matrix
step 2)  iterate to all nodes .
             if distance[node][node] < 0 
                       then negative cycle is present
#3

Oooo so it is different from dijkstra and bellman Ford. Can this algo work on negative edge cycle graph?

#4

@Senjuti256
what do u mean by work?
if graph will have negative cyle then we never reach to a saturation point.
weights will keep getting reduced on each iteration right?
solution will not exist if negative cyle is present

#5

Yea yea thanks. That only I asked that both Bellman and Floyd warshall algo work on graphs having negative edges but if there is a negative edge cycle thn no algo work because we don’t have any shortest distance thn right?

#6

yeah correct. . . . . . .

#7

About the steps that you have mentioned to detect whether the negative cycle is present or not. How does this work? I mean if the distance of any node of finally prepared dist matrix is less than 0 then it implies that there is a negative weighted edge but how does it imply a negative weight cycle?

#8

see distance of any node with itself is 0 right?

if it get negative after iteration then this implies that this node is a part of negative cycle becuase then only negative distance is possible.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.