<p>The mistake is in </p>

<blockquote>
  <p>This can only be true if there are no negative-weight cycles reachable from the source.</p>
</blockquote>

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

<p>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.</p>

CC BY-SA 3.0
2014-04-28T01:00:58.583Z
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
CC BY-SA 3.0
2014-04-27T16:44:26.333Z
2014-04-28T16:21:49.687Z
2014-04-28T16:21:49.687Z
Alex Dalyac
<p>Dijkstra's algo (for finding single-source shortest path) <strong>assumes</strong> 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. </p>

<p>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.</p>

<p>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. </p>

<p>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?</p>

<graph-theory><graph-algorithms><shortest-path>
Run Dijkstra's algorithm twice to detect negative-weight cycles?
Alex Dalyac
# Run Dijkstra's algorithm twice to detect negative-weight cycles?

(Asked by: username_0 on 2014-04-27)

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?

**Tags:** graph-theory, graph-algorithms, shortest-path

---

## 1 answers

### Answer by username_0 on 2014-04-27. Score: 9

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.

> **Comments:**
> **username_1**: 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.  

---

