41

Can we use Dijkstra's algorithm with negative weights?

STOP! Before you think "lol nub you can just endlessly hop between two points and get an infinitely cheap path", I'm more thinking of one-way paths.

An application for this would be a mountainous terrain with points on it. Obviously going from high to low doesn't take energy, in fact, it generates energy (thus a negative path weight)! But going back again just wouldn't work that way, unless you are Chuck Norris.

I was thinking of incrementing the weight of all points until they are non-negative, but I'm not sure whether that will work.

Kromster
  • 7,181
  • 7
  • 63
  • 111
orlp
  • 112,504
  • 36
  • 218
  • 315
  • 12
    http://en.wikipedia.org/wiki/Bellman-Ford_algorithm – Bart May 10 '11 at 21:15
  • 4
    Wikipedia has this to say: `Unlike Dijkstra's algorithm, the Bellman-Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s. (The presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed.)` – Rom1 May 10 '11 at 21:18
  • I find this : http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstra-algorithm to be a much better explanation – basarat Nov 05 '12 at 09:04
  • If you precompute the shortest path to each node (using Bellman Ford), subtract that from all incoming edges, and add that to all outgoing edges, then yes. You'll end up with a transformed (now directed) graph with all nonnegative weights that you can use Dijkstra's on. It's called Johnson's algorithm and it's the best way to determine the shortest path between every pair of points in a weighted graph, which costs |V| * O(dijkstras) + O(Bellman) = |V| * O(dijkstras) = |V| * (E + V log V) – RussellStewart Apr 04 '14 at 06:58
  • Also, this is precisely the type of problem that you would be able to solve by adding a constant factor to each node. If going up hill costs mgh energy, and going downhill reclaims 70% of mgh energy, then frame the cost of every transition of 30% * mg * (h2 - h1) going up, and 0 going down. Run dijkstra's to find the shortest path from the origin to every other point. Add back 70% * mg (h_x) for every node x, and then compute the minimum. – RussellStewart Apr 15 '14 at 18:14
  • Isn't a path, by definition, not supposed to contain a cycle? Every vertex in a path is distinct. – Myath Oct 29 '17 at 02:54
  • Does this answer your question? [Negative weights using Dijkstra's Algorithm](https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm) – user4157124 Apr 01 '22 at 15:58

7 Answers7

75

As long as the graph does not contain a negative cycle (a directed cycle whose edge weights have a negative sum), it will have a shortest path between any two points, but Dijkstra's algorithm is not designed to find them. The best-known algorithm for finding single-source shortest paths in a directed graph with negative edge weights is the Bellman-Ford algorithm. This comes at a cost, however: Bellman-Ford requires O(|V|·|E|) time, while Dijkstra's requires O(|E| + |V|log|V|) time, which is asymptotically faster for both sparse graphs (where E is O(|V|)) and dense graphs (where E is O(|V|^2)).

In your example of a mountainous terrain (necessarily a directed graph, since going up and down an incline have different weights) there is no possibility of a negative cycle, since this would imply leaving a point and then returning to it with a net energy gain - which could be used to create a perpetual motion machine.

Increasing all the weights by a constant value so that they are non-negative will not work. To see this, consider the graph where there are two paths from A to B, one traversing a single edge of length 2, and one traversing edges of length 1, 1, and -2. The second path is shorter, but if you increase all edge weights by 2, the first path now has length 4, and the second path has length 6, reversing the shortest paths. This tactic will only work if all possible paths between the two points use the same number of edges.

BartoszKP
  • 34,786
  • 15
  • 102
  • 130
Chiara Coetzee
  • 4,201
  • 1
  • 24
  • 20
  • 6
    Well, unless the mountain contains a [Penrose staircase](http://en.wikipedia.org/wiki/Penrose_stairs) I don't think a cycle of negative edges is ever going to occur. – orlp May 10 '11 at 21:26
  • 2
    Well answered! I'd like to point out that if the number of negative edges is limited, there are Dijkstra-based algorithms that might do a better job. For example, if there is only one negative edge from u to v, you could run Dijkstra on s and on v, and then take the minimum for each vertex between d[s] and d[s]+w(u, v)+d[v], giving a complexity of running Dijkstra twice. – Gilthans Jul 03 '12 at 11:36
  • Will modifying the distance to a better weight (ie. time) do the job? See my answer. – Karussell Oct 10 '12 at 11:34
  • 1
    @Karussell If your goal is to determine the fastest route, then of course using time is appropriate. If your goal is to determine the route that involves the least total work (in the physics sense) then the graph as described in the problem with negative weights on downhill slopes is appropriate. Similarly, if you wanted to compute electricity consumption of a vehicle with regenerative brakes, then a downhill slope could very well have a negative weight (braking while going down a hill actually charges the battery). – Chiara Coetzee Oct 10 '12 at 13:03
  • 2
    Nitpick: "As long as the graph does not contain a directed cycle of negative edges, it will have a shortest path between any two points" -- not true. A cycle with just one (very) negative edge, and the rest positive, can be an overall negative-weight cycle, and thus prevent the existence of shortest paths between some point pairs. – j_random_hacker Apr 29 '15 at 11:42
3

If you read the proof of optimality, one of the assumptions made is that all the weights are non-negative. So, no. As Bart recommends, use Bellman-Ford if there are no negative cycles in your graph.

You have to understand that a negative edge isn't just a negative number --- it implies a reduction in the cost of the path. If you add a negative edge to your path, you have reduced the cost of the path --- if you increment the weights so that this edge is now non-negative, it does not have that reducing property anymore and thus this is a different graph.

I encourage you to read the proof of optimality --- there you will see that the assumption that adding an edge to an existing path can only increase (or not affect) the cost of the path is critical.

Jacob
  • 34,255
  • 14
  • 110
  • 165
  • What about _"I was thinking of incrementing the weight of all points until they are non-negative, but I'm not sure whether that will work."_ – orlp May 10 '11 at 21:24
  • That will not work unless all paths traverse a constant number of edges. Otherwise, you will be relatively penalizing paths that traverse more edges than others. – recursive May 10 '11 at 21:32
  • @nightcracker - it won't. Consider this graph: `1->2 (cost 10); 1->3 (cost 2); 2->3 (cost -100); 3->4 (cost 2)`. You will add 101 to each edge, and get the minimum path from 1 to 4 as 1->3->4, but 1->2->3->4 is better. Dijkstra will miss that one however, because node 3 only gets expanded once. If you allow it to be expanded more than once, that will work, but that stops being Dijkstra and morphs into the Bellman-Ford algorithm. – IVlad May 10 '11 at 21:33
  • Do you have the link for the original proof by Dijkstra, possibly in dutch? He always wrote in dutch, and I'm lucky that it's my native language. – orlp May 10 '11 at 22:46
  • 1
    @nightcracker Google "dijkstra's algorithme correctheids bewijs" and you'll find it - and a lot of documentation in Dutch on the algorithm – rlc May 10 '11 at 23:55
2

There is actually an algorithm which uses Dijkstra's algorithm in a negative path environment; it does so by removing all the negative edges and rebalancing the graph first. This algorithm is called 'Johnson's Algorithm'.

The way it works is by adding a new node (lets say Q) which has 0 cost to traverse to every other node in the graph. It then runs Bellman-Ford on the graph from point Q, getting a cost for each node with respect to Q which we will call q[x], which will either be 0 or a negative number (as it used one of the negative paths).

E.g. a -> -3 -> b, therefore if we add a node Q which has 0 cost to all of these nodes, then q[a] = 0, q[b] = -3.

We then rebalance out the edges using the formula: weight + q[source] - q[destination], so the new weight of a->b is -3 + 0 - (-3) = 0. We do this for all other edges in the graph, then remove Q and its outgoing edges and voila! We now have a rebalanced graph with no negative edges to which we can run dijkstra's on!

The running time is O(nm) [bellman-ford] + n x O(m log n) [n Dijkstra's] + O(n^2) [weight computation] = O (nm log n) time

More info: http://joonki-jeong.blogspot.co.uk/2013/01/johnsons-algorithm.html

Evil Washing Machine
  • 1,293
  • 4
  • 18
  • 43
2

You can use Dijkstra's on a negative weighted graph but you first have to find the proper offset for each Vertex. That is essentially what Johnson's algorithm does. But that would be overkill since Johnson's uses Bellman-Ford to find the weight offset(s). Johnson's is designed to all shortest paths between pairs of Vertices.

http://en.wikipedia.org/wiki/Johnson%27s_algorithm

Justin
  • 4,196
  • 4
  • 24
  • 48
0

Actually I think it'll work to modify the edge weights. Not with an offset but with a factor. Assume instead of measuring the distance you are measuring the time required from point A to B.

weight = time = distance / velocity

You could even adapt velocity depending on the slope to use the physical one if your task is for real mountains and car/bike.

Karussell
  • 17,085
  • 16
  • 97
  • 197
0

Yes, you could do that with adding one step at the end i.e.

            If v ∈ Q, Then Decrease-Key(Q, v, v.d)
            Else Insert(Q, v) and S = S \ {v}.
Clarence Klopfstein
  • 4,682
  • 10
  • 33
  • 47
sa_nyc
  • 971
  • 1
  • 13
  • 23
-5

An expression tree is a binary tree in which all leaves are operands (constants or variables), and the non-leaf nodes are binary operators (+, -, /, *, ^). Implement this tree to model polynomials with the basic methods of the tree including the following:

  1. A function that calculates the first derivative of a polynomial.
  2. Evaluate a polynomial for a given value of x.

[20] Use the following rules for the derivative: Derivative(constant) = 0 Derivative(x) = 1 Derivative(P(x) + Q(y)) = Derivative(P(x)) + Derivative(Q(y)) Derivative(P(x) - Q(y)) = Derivative(P(x)) - Derivative(Q(y)) Derivative(P(x) * Q(y)) = P(x)*Derivative(Q(y)) + Q(x)*Derivative(P(x)) Derivative(P(x) / Q(y)) = P(x)*Derivative(Q(y)) - Q(x)*Derivative(P(x)) Derivative(P(x) ^ Q(y)) = Q(y) * (P(x) ^(Q(y) - 1)) * Derivative(Q(y))

the Tin Man
  • 158,662
  • 42
  • 215
  • 303
zile
  • 7
  • 1