Run Dijkstra's algorithm twice to detect negative-weight cycles?

Question

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?

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.