I was asked to give an example of a graph that has edges with negative weight, but Dijkstra's algorithm will still give us the correct output. It was part of a prove/disprove question. The claim was.. "If a graph has negative edges, Dijkstra's algorithm will return the wrong output".
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Does this answer your question? Dijkstra's algorithm for undirected graphs with negative edges $\endgroup$– xskxzrCommented Aug 21, 2021 at 3:36
-
3$\begingroup$ Two vertices, one edge, negative weight. Thinking of trivial examples might be a useful habit to develop. $\endgroup$– Eric TowersCommented Aug 21, 2021 at 20:34
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
4
Suppose graph $G$ is directed, and acyclic such that just some of edges of source $s$ have negative weight, hence Dijkstra's algorithm does work in a such case.
-
2$\begingroup$ It does not guarantee that Dijkstra's algorithm will work. Take a look at the graph that contains the following cycle: $s\rightarrow v\rightarrow s$ where $\rightarrow v$ costs $-10$ and $v\rightarrow s$ costs 5. In this case, Dijkstra's algorithm isn't correct and will get stuck in an infinite loop (it actually can return the correct answer, depending on how you implement the algorithm) $\endgroup$ Commented Aug 19, 2021 at 10:06
-
-
1$\begingroup$ It's true that if $G$ is directed, and every edge with a negative weight is leaving the source, and there are no cycles having negative total weight, then Dijkstra's algorithm will work correctly. But the proof of this is much more involved than given above. $\endgroup$ Commented Aug 20, 2021 at 18:16
-
$\begingroup$ Being directed and acyclic is not enough. If the graph is a directed tree then there is just one path between the source and any other node, so it's the shortest automatically and Dijkstra's algorithm would find it; is that what you were thinking of? $\endgroup$– kaya3Commented Aug 21, 2021 at 12:57
$\begingroup$
$\endgroup$
Take a look at the simplest possible example: Our graph has only two nodes: $s,t$, and a single edge between them.
In this example, it won't matter what is the cost of this single edge (it can be negative), and Djikstra will always return the only single path between $s$ and $t$: which is directly $s\rightarrow t$.
answered Aug 19, 2021 at 10:08
$\begingroup$
$\endgroup$
Yet another way to prove the existence is to take any graph G, and replace one edge E with weight W by two new edges and an intermediate node N. Let the first new edge have weight -W/2 and the other new edge +3W/2.
Any path through these two new edges will still have a contribution W from the two edges together . You still need to prove that Dijkstra works for paths that begin or end in the new node N, but that's fairly straightforward.
$\begingroup$
$\endgroup$
1
Dijkstra's algorithm sometimes works when there are negative weights, and sometimes not, others have given several examples. Allow me to give a few ideas that may make it easier to find an example on your own.
Dijkstra's algorithm never works when there is a negative weight cycle. If a graph has negative weights, but no negative weight cycles, it is possible to modify the graph into a graph where Dijkstra can be applied and the results transformed to find shortest paths in the original graph. One such technique is known as Johnson's algorithm. I think this fact makes it more intuitive that negative weights are not an essential problem for Dijkstra's algorithm, and so we should expect some examples where it just works.
answered Aug 20, 2021 at 9:53
-
1$\begingroup$ Johnson's algorithm actually does far more than that! Its fascinating how Jonson's algorithm managed to squeeze out a better solution for its required (slightly higher) running-time $\endgroup$ Commented Aug 20, 2021 at 10:50
$\begingroup$
$\endgroup$
2
One other setting where Dijkstra will always work is where the only negative edges in the graph are ones leaving the start node $s$ and there are no other edges leaving $s$. The idea is that the algorithm can’t be “surprised” by finding a path whose cost drops as more edges are added in. It’s a great exercise to prove that this indeed is the case; it’s basically a generalization of the regular proof of correctness for Dijkstra’s algorithm.
(This generalizes the excellent answer by @nir shahar.)
answered Aug 20, 2021 at 13:24
-
$\begingroup$ If you also require that there is no path from those nodes back to the starting node $s$ that is cheap enough, this will work. Otherwise - it is not guaranteed (it can work, depending on the precise implementation of Djikstra's algorithm) :) $\endgroup$ Commented Aug 20, 2021 at 16:16
-
$\begingroup$ @nirshahar Good point - my original wording was ambiguous. Answer updated! $\endgroup$ Commented Aug 20, 2021 at 20:01