# Floyd–Warshall algorithm on an undirected graph contains negative weight edges

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?

• Possible duplicate of Can Floyd-Warshall algorithm be used in an undirected graph with negative edges? – xskxzr Mar 23 '19 at 15:44
• @xskxzr The accepted answer is not as precise as the answer here. Thank you. – Abdulkader Mar 23 '19 at 16:02
• 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.) – David Richerby Mar 23 '19 at 18:08

• @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. – D.W. Mar 23 '19 at 3:16