0

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.

piet.t
  • 11,718
  • 21
  • 43
  • 52
jiqiudabao
  • 121
  • 1
  • 2

3 Answers3

1

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.

Henry
  • 42,982
  • 7
  • 68
  • 84
  • "The reason is that it is a greedy algorithm. Once it has chosen the minimum distance node it does not reconsider this choice." Actually, it does. Most implementations of Dijkstra have a line like "if (dist[u] + weight[u][v] < dist[v])", which does exactly this. – WeakestTopology Aug 23 '20 at 18:05
  • @WeakestTopology you overlooked the "Once it has chosen the minimum distance node" part. This decision is never revisited. – Henry Aug 24 '20 at 04:42
  • It will choose a minimum distance node at every iteration, that's not a problem. On your example, it will start with "start", put "end" and "x" in the queue, choose "end", remove "end" from the queue, choose "x", relax "end" and put it in the queue again. It's just going to be slower. – WeakestTopology Aug 24 '20 at 11:00
  • This line "if (dist[u] + weight[u][v] < dist[v])" does exactly this, it doesn't matter if v was the minimum distance node until now or not. – WeakestTopology Aug 24 '20 at 11:13
  • @WeakestTopology That's not how I understand Dijkstra's algorithm. – Henry Aug 24 '20 at 14:59
1

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.

Taylor
  • 11
  • 1
0

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.

U R
  • 490
  • 9
  • 15