Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What kind of cycle isn't allowed in Floyd–Warshall algorithm?

For example,

Let's say

1->2 costs 100
2->4 costs 600

So 1->2->4 costs 700

What if there was an edge from 4 to 3 costing -500 ? And a different edge from 3 to 4 costing 200

4->3 costs -500
3->4 costs 200

So 1->2->4->3->4 costs 400

Which is less than 700

So is 1->2->4->3->4 considered a shorter path than 1->2->4 ???

I understand that no cycles are allowed, this is an example of a path with no repeating edges.

What about vertices? If they repeat is it an allowable cycle in Floyd Warhsall?

Because I know there's different types of algorithms, one which allows cycles of one kind and disallows cycles from other kinds.

Can someone explain this to me? Answer the question of, is 1->2->4->3->4 considered a shorter path than 1->2->4 ???

Thank you all in advance.

Edit:

Here's a picture, showing you don't have to visit the same edge twice.

enter image description here

like image 604
ABCD123 Avatar asked Dec 02 '14 21:12

ABCD123


2 Answers

The Floyd–Warshall algorithm requires a graph with no negative cycles. In your example, 4->3->4 is a negative cycle because the sum of the weights over the cycle is -500 + 200 = -300.

like image 152
aardvarkk Avatar answered Nov 15 '22 03:11

aardvarkk


Floyd Warshall is an algorithm with constraint :graph with no negative cycle, if you want to find the shortest path in a graph with negative cycle you cant use Floyd Warshal, and this has a reason consider your graph with negative cycle 4->3->4 with cost -300. if you go one time through this cycle your cost reduce to 400 from 700, but why just stop there? go another time, and your cost will be 100, and again and again and again, it will cost you -200 , -500 , ... . You could do it forever and algorithm will never stop. This is why there is this constraint with no negative cycle in Floyd Warshall algorithm.

like image 42
Lrrr Avatar answered Nov 15 '22 04:11

Lrrr