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. :)