[Math] Dijkstra’s Algorithm on a Directed Graph with Negative Edges Only Leaving the Source

algorithmsgraph theory

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. 🙂

Best Answer

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.

BONUS

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.

Related Question