2
$\begingroup$

I'm struggling to think of such a network. According to the definition I'm working with:

Given a network $(V, A, w)$.

For all arcs $(u, v) \in A$ :

$\quad$ If $d[u, |V| - 1] + w(u, v) < d[v, |V| - 1]$:

$\quad\quad$ Print “Negative cycle!” and stop immediately

To me this implies the only way a negative cycle isn't detected is if all arcs from any $u$ to my $v$ must have a positive weight. How, then, could there be a negative cycle?

$\endgroup$
1
$\begingroup$

No, it is not possible. If there is a negative cycle in a network, it will be found by the step 3 of Bellman–Ford algorithm as described by Wikipedia.

Here is the reason given by Wikipedia.

Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. At each iteration $i$ that the edges are scanned, the algorithm finds all shortest paths of at most length $i$ edges (and possibly some paths longer than $i$ edges). Since the longest possible path without a cycle can be $|V|-1$ edges, the edges must be scanned $|V|-1$ times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length $|V|$ edges has been found which can only occur if at least one negative cycle exists in the graph.

For more detailed understanding, please read the proof of the correctness of Bellman-Ford as well as finding negative cycles by Bellman-Ford.


Here is one easy related exercise.

Exercise. Let $e_0, e_1, e_2, \cdots, e_{m-1}, e_m=e_0$ be a negative cycle whose number of vertices, $m$ is the smallest among all negative cycles. Show that it is a chordless cycle.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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