CODEWITHSUNDEEP
algorithmgraphdijkstradirected-acyclic-graphsbellman-ford
jiqiudabao
jiqiudabao

Reputation: 121

Can I use Dijkstra's algorithm on DAG with negative weighted edges?

I understand that Dijkstra's algorithm cannot be used for negative weight edges since it could mess up distances for vertices already in the cloud.

But what if the directed graph doesn't contain a cycle i.e directed acyclic graph (DAG)? I think Dijkstra's algorithm can be used even with negative weighted edges to find the minimum cost path.

Upvotes: 0

Views: 3997

Answers (3)

U R
U R

Reputation: 530

The algorithm cannot be used even if the negative edges are made non-negative by finding the lowest edge weight(which will be the lowest negative number in a graph with negative edges) and adding a number which is absolute value of the lowest edge weight to all the edges in the graph

I was curious about whether making the edges non-negative would work.But it wont and this other stackoverflow answer cleared my doubt.

Upvotes: 0

Taylor
Taylor

Reputation: 11

Generally, Dijkstra's algorithm cannot be used to graph with negative edge lengths. However, there can be a special case. If all negative edges in the graph are connected to the starting point (also works for the destination if you flip the starting point and the destination in an undirected graph). Dijkstra's algorithm will also offer the shortest path.

The reason for this is that Dijkstra's algorithm always picks the edge that has the minimum distance from the starting node. The core part is: In non-negative weights case, adding more edges in a path, this path will only increase (at least won't decrease). However, if negative lengths are introduced, adding more edges in a path may lead to decreasing the path length.

In the following example, if you start from s to t, using Dijkstra's algorithm, it will not work because edge(v, t) reduces the length of the path.

An example

However, if we start from t to s using Dijkstra's algorithm, It will pick the edge(v, t) instead of (s,t) and later it will pick (s, v). It will work because only the edges incident to the starting node are negative will not hurt the global shortest distances. In the later iteration, only non-negative edges will be picked and adding more edges will surely increase the length.

In general, it is safe to say that Dijkstra's shortest algorithm will not work in graphs with negative edge lengths.

Upvotes: 1

Henry
Henry

Reputation: 43728

No, it cannot be used when there are negative weights. The reason is that it is a greedy algorithm. Once it has chosen the minimum distance node it does not reconsider this choice. Negative weights would allow that some other node later in the algorithm becomes lower.

Here is a simple counter example:

start  -- 1 ----------> end
    |                    ^
    \ -- 2 --> x -- -3 --/

In this case the algorithm gives you the direct path of weight 1 instead of the shorter path via node x with weight -1.

Upvotes: 1

Related Questions