According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances to all vertices in a negative cycle, as well as the distances to the vertices reachable from this cycle, are not defined. So in the all-pairs shortest path problem, can we say the Floyd–Warshall algorithm also doesn't work on an undirected graph contains negative weight edges for the same reason?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Possible duplicate of Can Floyd-Warshall algorithm be used in an undirected graph with negative edges? $\endgroup$– xskxzrCommented Mar 23, 2019 at 15:44
-
$\begingroup$ @xskxzr The accepted answer is not as precise as the answer here. Thank you. $\endgroup$– AbdulkaderCommented Mar 23, 2019 at 16:02
-
$\begingroup$ Agreed -- the answer here is better and we should close the other question as a duplicate of this one. This will help people find the better answer. (It doesn't matter that the other one was posted first.) $\endgroup$– David RicherbyCommented Mar 23, 2019 at 18:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
Perhaps it is useful to be more precise about what is meant by "doesn't work". If the directed graph contains a cycle of negative weight, then the notion of shortest path is not well-defined. Therefore, it makes no sense to run a shortest-path algorithm on such a graph. There's no hope for any algorithm to output the shortest path in such a graph, because there is no shortest path.
If you have an undirected graph with negative-weight edges, and you convert it to a directed graph in the obvious way, you'll end up with a directed graph that contains negative-weight cycles. Consequently, no shortest path algorithm has any hope of success at finding shortest paths: there is no directed path (in the directed graph). It doesn't matter what algorithm you are considering using.
Basically, the conversion from undirected graph to directed graph, in shortest path problems, is only correct if all weights are non-negative. If all edge weights are non-negative, then the shortest path in the undirected graph corresponds to the shortest path in the directed graph you obtain in this way. However, if the undirected graph has negative-weight edges, then there is no longer any such correspondence, so the conversion is not useful.
-
$\begingroup$ It occurs to me that a path in a graph is usually defined as a simple path, that is, all vertices of which are distinct. Then the shortest path does make sense even in a graph with cycles of negative weights, although not perfect or not much. Have you ever thought of that situation? (wait, I just recall that is a NP-hard problem.) $\endgroup$– John L.Commented Mar 23, 2019 at 1:37
-
$\begingroup$ Thus, for each Connected Component (CC) contains at least one negative-weight edge in an undirected graph, there is no shortest path between any pair of vertices in this CC. Right? $\endgroup$ Commented Mar 23, 2019 at 2:12
-
$\begingroup$ @Apass.Jack, agreed! Finding the shortest simple path from $s$ to $t$ in a graph with negative-weight edges is NP-hard (by a reduction from Hamiltonian path). Finding the shortest simple path from $s$ to $t$ in a graph with no negative-weight edges is equivalent to finding the shortest path from $s$ to $t$ (simple or not). Finding the shortest path from $s$ to $t$ (simple or not) in a graph with no negative-weight edges can be done in polynomial time. $\endgroup$– D.W. ♦Commented Mar 23, 2019 at 3:16
-
$\begingroup$ @Abdulkader, Yes. There won't be a shortest path in the undirected graph if you can traverse that edge multiple times (e.g., go back and forth on it as many times as one desired). There will be a shortest simple path in the undirected graph, but that problem is NP-hard to solve when there can be negative-weight edges; and that transformation to a directed graph no longer behaves like we'd want it to when you have negative-weight edges. I hope I'm not just making this more confusing... $\endgroup$– D.W. ♦Commented Mar 23, 2019 at 3:19
-
$\begingroup$ @D.W. Can you explain why finding shortest simple path in weighted undirected graph with some negative edge weight, can be NP-hard by reduction fromHamiltonian path? Thanks $\endgroup$– user139105Commented Aug 2, 2021 at 9:04