Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Nope, you can still have a negative cycle here. –  dtldarek Mar 25 '12 at 18:54
    
I'm assuming that there are no negative cycles. –  Robert Mar 25 '12 at 19:06
    
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). –  dtldarek Mar 25 '12 at 19:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.