So i know that it cannot be used if the directed graph has negative cycle, but what about the undirected graphs with negative edges?
is it going to always work, or sometimes or never?
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ Possible duplicate of Floyd–Warshall algorithm on an undirected graph contains negative weight edges $\endgroup$– David RicherbyCommented Mar 23, 2019 at 18:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Floyd–Warshall can be used to detect the presence of negative cycles in directed graphs. This aspect has been widely used in the scheduling community in the form of detecting consistency of a simple temporal network. To answer your question, the values output by Floyd–Warshall will be correct even in the presence of negative edges as long as there are no negative cycles.
-
$\begingroup$ But if there is a negative edge on a undirected graph, that means there is a negative cycle right? i mean shouldn't we convert the undirected edges to 2 directed edges? $\endgroup$– John PCommented Mar 20, 2018 at 13:16
-
$\begingroup$ Yes, you would need to convert the undirected edges to directed edges. I apologize, I dint read your question properly earlier. The following may be helpful. I guess you are interested in computing shortest simple paths between vertices. It is known that when there are negative cycles, the problem of computing shortest paths is NP-Complete (can be reduced from longest path problem). $\endgroup$ Commented Mar 20, 2018 at 14:24