patternMinor
Dijkstra's algorithm for undirected graphs with negative edges
Viewed 0 times
dijkstraedgeswithgraphsalgorithmundirectedfornegative
Problem
INPUT: "an undirected, weighted graph (negative weights allowed)"
Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work?
As far as i understood it only fails by directed graphs in case of negative edges.
Am i right ?
Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work?
As far as i understood it only fails by directed graphs in case of negative edges.
Am i right ?
Solution
It's not just Dijkstra's algorithm that doesn't work. Other standard shortest-path algorithms like Bellman-Ford don't work on undirected graphs with negative edges either.
The problem is that these algorithms compute a shortest path tree rooted at the source vertex $s$. Specifically, both algorithms assign a predecessor (or parent) to each vertex $v$, which is the second-to-last vertex on the shortest path from $s$ to $v$. This works for undirected graphs with positive edges and arbitrary directed graphs, because in those graphs, any prefix of a shortest path is another shortest path.
But shortest paths in undirected graphs with negative edges don't necessarily define trees. Consider the following simple example:
The shortest path from $s$ to $x$ passes through $y$ and has length zero. Symmetrically, the shortest path from $s$ to $y$ passes through $x$ and has length zero. Both of these shortest paths use the edge $xy$, but in opposite directions. The edges $sx$ and $sy$ are prefixes of shortest paths, but they are not themselves shortest paths.
Shortest paths can still be computed in polynomial time in these graphs (provided they have no negative cycles), but the algorithms are much more complicated.
The problem is that these algorithms compute a shortest path tree rooted at the source vertex $s$. Specifically, both algorithms assign a predecessor (or parent) to each vertex $v$, which is the second-to-last vertex on the shortest path from $s$ to $v$. This works for undirected graphs with positive edges and arbitrary directed graphs, because in those graphs, any prefix of a shortest path is another shortest path.
But shortest paths in undirected graphs with negative edges don't necessarily define trees. Consider the following simple example:
The shortest path from $s$ to $x$ passes through $y$ and has length zero. Symmetrically, the shortest path from $s$ to $y$ passes through $x$ and has length zero. Both of these shortest paths use the edge $xy$, but in opposite directions. The edges $sx$ and $sy$ are prefixes of shortest paths, but they are not themselves shortest paths.
Shortest paths can still be computed in polynomial time in these graphs (provided they have no negative cycles), but the algorithms are much more complicated.
Context
StackExchange Computer Science Q#7649, answer score: 6
Revisions (0)
No revisions yet.