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 fromw
tov
,v
must come first.Here it continues to be a contradiction because otherwise, there would be a negative weighted path from
w
tov
, which means it uses a negative edge, that is an edge fromsource
, which is absurd because that would meandist[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
totarget
uses no return edges tosource
, thus the shortest path can be selected from the set $P$ of those paths which don't return tosource
ever.It is also clear that every path in $P$ uses exactly once one of the outgoing edges from
source
. (We may assumesource
is not the same node astarget
).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.