Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Dijkstra's algo (for finding single-source shortest path) assumes that once a vertex has been chosen for expansion (aka exploration), its shortest path has been found. This can only be true if there are no negative-weight cycles reachable from the source.

Therefore, I was thinking that in order to detect a negative-weight cycle, we could run Dijkstra's algorithm a 2nd time, but instead of initialising the vertex distances to -infinity, we use the ones found by the 1st iteration. If at any point during this 2nd iteration, there is a distance update, the assumption above is violated, therefore there is a negative weight cycle.

There must be a mistake in my reasoning, because if this works, it would have same time complexity as Dijkstra's algo, which would be better than the Bellman-Ford algorithm, which is the textbook algorithm for solving the single-source shortest-path in potential presence of negative weight cycles.

Is my mistake that a 2nd iteration may lead to no distance updates even in the presence of a negative weight cycle? If so, could someone provide such an example?

share|improve this question
add comment

1 Answer 1

The mistake is in

This can only be true if there are no negative-weight cycles reachable from the source.

Actually, this can only be true if there are no negative-weight edges reachable from the source.

So the "double Dijkstra" suggested above may wrongly return false in a graph with negative-weight edges but no negative-weight cycles, whereas Bellman-Ford will correctly return true.

share|improve this answer
4  
Well, it's sometimes possible for Dijkstra to get the correct answer even when there are negative edges. So "will wrongly return false" is a little strong: it might return false, or it might not. –  David Eppstein Apr 28 at 1:00
    
true! thanks, edited –  Alexandre Holden Daly Apr 28 at 16:22
add comment

Your Answer

 
discard

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

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