50
$\begingroup$

I know this is probably very basic, I just can't wrap my head around it.
We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph.

My professor said this algorithm will not work on a graph with negative edges, so I tried to figure out what could be wrong with shifting all the edges weights by a positive number, so that they all be positive, when the input graph has negative edges in it.

For example, let's consider the following input graph:
input graph
Now if I'll add 3 to all edges, it's obvious that the shortest path (between $s$ and $t$) has changed: graph after adding 3
Thus this kind of operation might result in wrong output.

And this, basically, what I don't get. Why does this happen? Why is shifting the values has such a dramatic effect on the shortest path? This is totally counter-intuitive, at least for me.

Your thoughts?

Improve this question
$\endgroup$
4
  • 12
    $\begingroup$ The paths might have different amounts of edges in them, and so adding constant values to all edge weights will distort paths weights differently. Look into Johnson's algorithm, that should give you a good idea about this problem. $\endgroup$
    – G. Bach
    Commented Jan 16, 2014 at 19:05
  • $\begingroup$ For those arriving here: See also cs.stackexchange.com/q/52080/755. $\endgroup$
    – D.W. ♦
    Commented Jan 21, 2016 at 11:22
  • $\begingroup$ Notice that a graph with negative edge weights might not have a shortest walk. Consider a graph with two nodes, A and B weight(AB) = -1. There are walks from A to B of weight -1, -3, -5, ... . If all weights are positive, then the shortest walk is a path, so we don't have to worry about the difference. If we have negative weights, we have to be very careful about what we want; the Bellman-Ford and Floyd-Warshall algorithms do different things. $\endgroup$
    – Max
    Commented Jul 28, 2016 at 22:02
  • $\begingroup$ "This is totally counter-intuitive." This is another example that intuition cannot be trusted especially when you are coming to a new field. $\endgroup$
    – John L.
    Commented Jan 5, 2019 at 18:44

3 Answers 3

Reset to default
42
$\begingroup$

Dijkstra relies on one "simple" fact: if all weights are non-negative, adding an edge can never make a path shorter. That's why picking the shortest candidate edge (local optimality) always ends up being correct (global optimality).

If that is not the case, the "frontier" of candidate edges does not send the right signals; a cheap edge might lure you down a path with positive weights while an expensive one hides a path with negative weights.

For details, I recommend you check out a correctness proof and try to do it with negative weights; observe where it breaks.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for your to the point explanation and clear wording. $\endgroup$
    – Avv
    Commented Sep 19, 2021 at 19:06
14
$\begingroup$

Adding a constant amount to each edge length can change the shortest path for the simple reason that it increases the length of a path with many edges by more than it increases the length of a path with only a few edges.

For a simple case, consider the graph with vertices $\{a,b,c\}$ and edges $\{ab,bc,ac\}$, where $ab$ and $bc$ have length $1$ and $ac$ has length $3$. The shortest $a$–$c$ path is $abc$ with length $2$. However, if you increase each edge's length by $2$, then the length of $abc$ increases by $4$, while the length of $ac$ increases only by $2$. So, now, $ac$ is the shortest path, with length $5$ versus $6$.

Improve this answer
$\endgroup$
4
$\begingroup$

Actually , Dijkstra's algorithm fails to work for most of the negative weight edged graphs , but sometimes it works with some of the graphs with negative weighted edges too provided the graph doesn't have negative weight cycles , This is one case in which dijkstra's algorithm works fine and finds the shortest path between whatever the point u give

And adding some positive number X to all the edges just to make them positive doesn't result in correct answer. Shortest distance can be P through one path and P1 through another path containing number of edges N and N1 respectively , suppose P > P1 but P1 has more edges than P , that might actually make P less than P1 since P's distance is added to N * whatever the actual number u added to all the edges and thus results in a wrong answer!!

edit: Yes , Dijkstra also works for some of the graphs with negative weighted cycle too as long as the element that is already considered shortest is not relaxed anymore.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ There are instances of the shortest path problem with negative weight cycles where Dijkstra gives the correct answer. It requires (1) that the destination is not reachable from the cycle, and (2) that the destination is reached before any element of the cycle. $\endgroup$
    – Peter Taylor
    Commented Aug 30, 2018 at 9:58
  • $\begingroup$ @PeterTaylor Yes , edited . thank you . $\endgroup$
    – jeshwanth chowdary
    Commented Sep 20, 2018 at 5:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.