I've been trying to figure out if Dijkstra's algorithm will always succeed on a directed graph that can have edges with negative weights leaving the source vertex only (all other edges are positive), assuming no negative cycles.

I'm inclined to believe that Dijkstra's algorithm WILL always work in this case, since the fact that only edges leaving the source can be negative seems to prevent the issue where the algorithm would not take into account negative edges further along in the graph when finding the shortest paths to a given node, but I just wanted to get a sanity check to make sure that I wasn't completely missing something. That, and I've been unable to come up with a counter-example that would disprove this.

Any input would be greatly appreciated. :)

  • 2
    $\begingroup$ Nope, you can still have a negative cycle here. $\endgroup$ – dtldarek Mar 25 '12 at 18:54
  • $\begingroup$ I'm assuming that there are no negative cycles. $\endgroup$ – Robert Mar 25 '12 at 19:06
  • $\begingroup$ What you need to prove is that the shortest path from source to those vertices is the one by those edges. If you have no negative cycles, then you can add a constant to all outgoing edges from the source and have them positive with no worries (only subtract that constant from the result). $\endgroup$ – dtldarek Mar 25 '12 at 19:15

It does work just the way you think!

Look at the proof at wikipedia. The fact that all the edges are assumed positive is used when they say that dist[w]>dist[v] is a contradiction because as there can not be a negative weighted path from w to v, v must come first.

Here it continues to be a contradiction because otherwise, there would be a negative weighted path from w to v, which means it uses a negative edge, that is an edge from source, which is absurd because that would mean dist[w]>dist[w,source], i.e. a negative cycle.


I'll proof that the approach proposed in @dtldarek's comment is also correct.

  • It is trivial that the shortest path from source to target uses no return edges to source, thus the shortest path can be selected from the set $P$ of those paths which don't return to source ever.

  • It is also clear that every path in $P$ uses exactly once one of the outgoing edges from source. (We may assume source is not the same node as target).

Therefore by adding a constant $K$ to every outgoing edge from source so that they are all positive, all the paths in $P$ will increase their lengths by $K$. If we call $P'$ this set of modified paths, we can claim

$min\{length(p) : p \in P\} \\ =min\{length(p)+K-K : p \in P\} \\ =min\{length(p)+K : p \in P\}-K \\ =min\{length(p') : p' \in P'\}-K$

and conclude that it suffices running dijkstra on the modified graph and substrating K.

  • $\begingroup$ You're assuming that there are no negative cycles through the origin, right? (A comment said you can assume so, so that's fine.) $\endgroup$ – David K Apr 6 '16 at 13:04
  • $\begingroup$ Yes, that's exactly what I assume $\endgroup$ – Carlos Pinzón Apr 6 '16 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.