2

Now I know Dijkstra won't work if the graph contains negative weight edges. But there is an exception to this. (Only the edges that leave the source can have negative weights while all the other edges must be positive.)

I want to be able to prove this. I don't know how to get started with this. I've made some diagrams and in all those Dijkstra ended up working perfectly but I don't understand on how I can prove this?

So what I actually want is someone to prove that Dijkstra will work in this case or won't (Only the outgoing edges from the source are negative.)

Plus the graph can't contain any cycles which involve the source.

S. Salman
  • 590
  • 1
  • 6
  • 22
  • 5
    The exception as is, is not true. Consider a graph `a->b->c->a` where `a` is the source, and `w(a,b) = -5, w(b,c)=w(c,a)=1` The graph has a negative cycle, and there is no shortest path to any node. – amit May 04 '15 at 09:29
  • Do you perhaps mean that additionally no cycles of negative length must exists? – Codor May 04 '15 at 09:30
  • 2
    possible duplicate of [why Dijkstra's algo does not work for negative weight edges](http://stackoverflow.com/questions/13159337/why-dijkstras-algo-does-not-work-for-negative-weight-edges) – Pham Trung May 04 '15 at 09:31
  • Sorry I need to mention that there are no cycles in the graph which involve the source. – S. Salman May 04 '15 at 09:32
  • While I'm flattered for the link - this is no a dupe. He does not ask why it does not work for general case he asks for showing the claim does not hold for specific exception. – amit May 04 '15 at 09:32
  • @George Adams Please be more precise. Do you mean to forbid cycles of negative length altogether or just cycles which contain the source? – Codor May 04 '15 at 09:34
  • 1
    @Codor If the only negative edges are leaving the source, the two claims are equivalent. – amit May 04 '15 at 09:35
  • The only edge that can be negative are the ones which leave the source AND there are no negative cycles which involve the source. – S. Salman May 04 '15 at 09:35

2 Answers2

3

First note that if there is no cycle involving the source, we can trim the graph for any edges incoming to the source, and it will not affect the result, the vertices that lead to the source will not be reached in Dijkstra's algorithm anyway (since otherwise, there is a cycle involving the source).

From now on, we'll assume there is no incoming edge to the source.

Note that the claim needed for relaxation step (triangular inequeality): d(u,v) <= d(u,x) + w(x,v) must hold (vacuously) for each w(x,v) < 0, the only u where there exists a path from u to x (which is the source) is u=x=source, and the path is the empty path.

This leads us to d(u,x) + w(x,v) = 0 + w(x,v) = w(u,v) = d(u,v) (where u is the source), and the inequality still holds.

amit
  • 175,853
  • 27
  • 231
  • 333
1

You can simply convert the general initial instance D into a feasible instance D' (i.e., one containing only positive edge values) and then show that Dijkstra's algorithm behaves the same on both instances. From this you can conclude that Dijkstra's algorithm is correct on instances of the form of D.

The following are the details:

You convert D to D' by inserting a "super source" s' which has only one edge -- an outgoing one to s with the distance d(s',s) = -min{d(s,x)|x is a node}. This instance is equivalent to one where d(s',s) is added to all the outgoing edges of s, which we call D'; it has only positive edge weights.

The behaviour of Dijkstra's algorithm on D and D' is the same as the ordering of the distances in the queue stays the same and therefore the same nodes are settled with the same (shifted) distances etc. Note that in this argument we implicitly use that there is no (negative) cycle containing s.

Because we know that Dijkstra's algorithm on D' finds the correct distances for the transformed graph and the structure of the shortest paths of D and D' must be the same we can conclude that Dijkstra's algorithm on instances of the form of D is correct.

Note: You can always use a so called Johnson Shift to let Dijkstra's algorithm perform correctly on graphs without negative cycles. You can also use a Johnson Shift for the proof but that wouldn't be self-contained.

maybeshewill
  • 3,824
  • 1
  • 15
  • 8