add cycles with negative weights check in Floyd-Warshall

0
votes

This is the pseudo-code for the Floyd-Warshall algorithm for shortest paths detection: enter image description here

I was wondering if it would be possible to add a check that will test if there are no cycles with negative weights?

I think it is possible, but I do not know how to check.

1
algorithmshortest-pathfloyd-warshall
That looks like a pseudocode for Bellman Ford, which of the two algorithms are you referring to? - Dario Petrillo
@DarioPetrillo sorry, I updated the question - Tryer outer

1 Answers

1
votes

Take the sum of all negative weights in the graph.

You have a negative cycle if and only if you find a path to a weight that is below that minimum.