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.
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
.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With