13

Will Dijkstra's Algorithm work if the digraph has only one negative weight edge and does not contain negative weight cycles?

jsh6303
  • 2,010
  • 3
  • 24
  • 50
  • possible duplicate of [Negative weights using Dijkstra's Algorithm](http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm) – Jerry Coffin Nov 21 '13 at 19:52
  • 3
    @JerryCoffin- I don't think this is a duplicate. This question asks about Dijkstra's algorithm with a very specific restricted set of negative edges, while the original question is about why Dijkstra's algorithm doesn't work on general graphs with negative edges. – templatetypedef Nov 21 '13 at 19:56

9 Answers9

16

No. Dijkstra's algorithm is greedy. It assumes path weights are strictly increasing.

Consider the following graph. S→A→E is optimal, but the Dijkstra's will return S→B→E.

troublesome graph

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
  • I think this counter-example is wrong - `A` vertex will be popped-out at last and then the algorithm will relax the edge `A-E` and so the chosen path will be `S->A->E` as expected. – Elimination Sep 07 '16 at 14:56
  • 1
    Once S→B→E is found Dijkstra's doesn't keep searching. That's what it means to be greedy. It takes the first solution it finds and doesn't look for additional, better ones. When all weights are non-negative there won't be any better ones. – John Kugelman Sep 07 '16 at 15:30
  • Wrong (As far as I can tell): I reviewed the algorithm presented at the CLRS book. **The algorithm stops when the priority queue is empty**. Therefore, when `A` will be popped out of the p-queue we will relax the edge `A->E` as I said above. – Elimination Sep 07 '16 at 16:35
  • 1
    If you want the shortest path between S and every node in the graph, you process the entire queue. If you only care about the path from S to E, you stop as soon as you find E. – John Kugelman Sep 07 '16 at 17:33
  • Maybe, but the classic form of the algorithm (i.e. the one in CLRS) stops when the p-queue is empty. – Elimination Sep 08 '16 at 12:49
2

Not necessarily. In this earlier answer, I gave an example of a graph with no negative cycles and one negative edge where Dijkstra's algorithm doesn't produce the correct answer. Therefore, Dijkstra's algorithm doesn't always work in this case.

Hope this helps!

Community
  • 1
  • 1
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
2

No. Dijkstra is greedy algorithm. Once it added an edge, it never looks back.

Vallabh Patade
  • 4,960
  • 6
  • 31
  • 40
2

No. Consider the following simple counterexample, with just 3 nodes, S (start), A, and B.

w(S, A) = 1
w(S, B) = 2
w(B, A) = -2

The algorithm will fix the distance for A first (cost 1), but it is cheaper to go there via B (cost 0).

Vincent van der Weele
  • 12,927
  • 1
  • 33
  • 61
  • I think it's wrong; the `B` vertex will be popped out of the priority-queue at last and then we will relax the edge `B->A`. Note that the algorithm stops when the p-queue is empty! – Elimination Sep 07 '16 at 16:40
  • @Elimination Dijkstra's generates a spanning tree. The shortest path from S to A is `S->B->A` (weight 0). The shortest path from S to B is `S->A->B` (weight -1). These paths cannot both be in the spanning tree, because it wouldn't be a tree. – Vincent van der Weele Sep 07 '16 at 17:12
2

Since Dijkstra's algorithm is greedy, it won't work with negative weights. U need some other algorithm like Bellman-Ford Algorithm for this purpose.

But, if you still want to use Dijkstra's Algo, there is a known way. In this method, you need to reassign costs, so that all become positive.

Here it is:

Suppose there is an edge from u to v. And the cost of the edge is cost(u,v).

u(d(u))------>v(d(v))

Define:

new_cost(u,v) = cost(u,v) + d(u) - d(v)

This is guaranteed to be positive since, 

d(v) < d(u) + cost(u,v)

Now, we can apply Dijkstra's algorithm normally, only difference being, in the cost of the new path, which will be (say the path is in between s' and t')

= original cost of the same path + d(s') - d(t')
Ranveer
  • 6,683
  • 8
  • 45
  • 92
  • Can you describe where you got that info from (redesigning costs) scientifc paper? author? Because I heard from a scientist, specialized on Dijkstras Algo, that many have tried to use Dijkstra with negative weights but none really have succeeded. – AlexWien Nov 22 '13 at 15:43
  • I am not using Dijkstra's algorithm on negative weights. It's simply not possible. I am simply using mathematical manipulation to change the costs themselves. If you observe carefully, the new and old costs would only vary by a constant. – Ranveer Nov 22 '13 at 15:53
2

You can not apply Dijkstra's algorithm directly to a graph with a negative edge as some of the other answers have correctly noted.

There is a way to reweigh the graph edges given that there are no negative cycles in the original graph. It's the same technique used in Johnson's algorithm where first you run one instance of Bellman-Ford's algorithm to get the weights h(v) for each vertex v. Then you modify each edge w(u,v) to w(u,v) + h(u) − h(v) which is guaranteed to be positive so you end up with a new graph with only positive edges on which you can run Dijkstra's algorithm.

Section XV. from the Coursera Algorithms class explains it much better than me.

The only issue with applying that technique for the single source shortest path problem is that reweighting with Bellman-Ford takes O(mn) time which is slower than Dijkstra's O(m log(n)). So you are better off just running Bellman-Ford for your original graph.

Daniel
  • 26,899
  • 12
  • 60
  • 88
2

Dijkstra's algorithm will work with a single negative edge as long as you start from the node which has that negative edge as an outgoing edge.
By starting with the smallest valued edge of the graph, you can no longer decrease the total cost by considering other edge weights (Which is how Dijkstra's algorithm works)

kerem
  • 2,699
  • 1
  • 32
  • 37
EhH17
  • 21
  • 1
1

No, Dijkstras Algorithm is well known to not work with negative weights. In case you need negative weights use Bellman-Ford algorithm.

AlexWien
  • 28,470
  • 6
  • 53
  • 83
0

WHY Dijkstra Can Fail It's Simple

because the Shortest Path Should Be : distance(s, vi) ≤ distance(s, vk )

For Exemple we have this Graph :

A---->B with Cost 2 B--->C with Cost Minus 4 the condition was False Now because Distance from A to B > Distance B to C

Ach Ref
  • 1
  • 1
  • 1