CODEWITHSUNDEEP
algorithmdata-structuresdijkstra
jsh6303
jsh6303

Reputation: 2040

Does Dijkstra's algorithm apply even if there is only one negative weight edge?

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

Upvotes: 13

Views: 4536

Answers (9)

EhH17
EhH17

Reputation: 21

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)

Upvotes: 2

Ach Ref
Ach Ref

Reputation: 1

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

Upvotes: 0

Daniel
Daniel

Reputation: 27589

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.

Upvotes: 2

John Kugelman
John Kugelman

Reputation: 361625

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

Upvotes: 16

Ranveer
Ranveer

Reputation: 6863

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')

Upvotes: 2

AlexWien
AlexWien

Reputation: 28727

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

Upvotes: 1

Vincent van der Weele
Vincent van der Weele

Reputation: 13177

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).

Upvotes: 2

Vallabh Patade
Vallabh Patade

Reputation: 5110

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

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372814

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!

Upvotes: 2

Related Questions