3

Dijkstra's Algorithm fails when in a graph we have edges with negative weights. However, to this rule there is an exception: If In a directed acyclic graph only the edges that leave the source node are negative (all the other edges are positive), then we can successfully use Dijkstra's Algorithm.

Now my question is, what if in the above exception the graph has a cycle? I believe Dijkstra won't work, but I cannot come up with an example of a directed graph that has cycles, and the only negative edges are those leaving the source node which does not work with Dijkstra. Anyone can suggest an example?

FranXh
  • 4,481
  • 20
  • 59
  • 78
  • 1
    Why do you think it will fail in this case? Note that the negative edges are NOT part of any cycle, since they are out edges from a *source* – amit Oct 10 '12 at 00:03
  • What if there is a cycle that involves the first child of the source node? Would that be a problem? – FranXh Oct 10 '12 at 00:05
  • My intuition says no, but I need to think about how to prove this. – amit Oct 10 '12 at 00:08
  • I have been trying to find a counter example unsuccessfully.... – FranXh Oct 10 '12 at 00:08
  • 1
    Related: http://stackoverflow.com/questions/5956534/dijkstras-algorithm-with-negative-weights – Andrew Tomazos Oct 10 '12 at 00:15
  • 1
    Of course, if there is a cycle with negative weight, then there is no minimum-weight path and the algorithm will loop forever. (Just so that it is explicitly stated.) – Daniel Fischer Oct 10 '12 at 15:40

1 Answers1

10

In the scenario you describe, Dijkstra's algorithm will work just fine.

The reason why it fails in the general case with negative weight since it greedily chooses which node to "close" at each step, and a closed node is never reopened.

Now, assume the source s has k out edges, to k different nodes.
Let the order of them be v_1, v_2, ..., v_k (v_1 being the smallest). Note that for each v_i, v_j such that i < j - there will be no path from s to v_i through v_j with a "better" cost then v_i, thus - the order of investigating these first nodes will never change. (and since it doesn't change, no way a later node will be entered to "closed" before the shortest path is indeed found).

Thus, at overall - no harm is done - once an edge is in the "closed" - you will never find a "shorter" path to it, since the negative edges are only from the source.

In here I assume the source in your question means d_in(source)=0, same as a "source" in a DAG.
If you mean out of the source vertex, it could be a problem since look at a 2 vertices graph such that w(s,t) = -2, w(t,s)=1 - there is a negative cycle in the graph. So, in order to the above explanation to work - you must assume d_in(s) = 0

amit
  • 175,853
  • 27
  • 231
  • 333