2
$\begingroup$

The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle?

For instance, say I have the below example going from initialization state through the first iteration and on to the second.

Initial state

    (0)S----(1)----B(inf)
        \         /
        (1)    (-1)  
          \     /
           \   / 
             C(inf)

First phase

...Check edges...
S->B
D[S] + 1 < D[B] = 0 + 1 < inf => True => Update D[B]

B->C
D[B] + (-1) < D[C] = 1 + (-1) < inf => True => Update D[C]

    (0)S----(1)----B(1)
        \         /
        (1)    (-1)  
          \     /
           \   / 
             C(0)

Second phase when checking for negative cycles

...Check edges...
...Skipping to check B->C...
B->C
D[B] + (-1) < D[C] = 1 + (-1) < 0 => False 



    (0)S----(1)----B(1)
        \         /
        (1)    (-1)  
          \     /
           \   / 
             C(0)

Shouldn't the last check between B->C be true to detect the negative cycle? i.e. Shouldn't we use less-than-or-equal-to (≤) rather than (<)?

$\endgroup$
  • $\begingroup$ The cycle you given has weight 1+1+(-1)=1, which is positive... $\endgroup$ – xskxzr Sep 14 at 3:55
  • $\begingroup$ Thank you for pointing that out. It appears I didn't fully understand what a negative cycle meant. $\endgroup$ – alex Sep 14 at 15:47
1
$\begingroup$

First of all, let me clarify a few points about your example:

  • Bellman-Ford-Moore consists of two phases, stages or steps, each one consisting of a number of iterations as they are implemented with loops. The first phase computes the cost of the shortest-path to reach each vertex from the start vertex and it consists of two nested loops; the second one consists of a single loop which checks whether there are negative cycles or not. I mention this because it seems to me that you refer to the phases as iterations.
  • Let me also note that in the first phase you skip the evaluation of reaching $S$ from $C$. I assume you just simply avoid making the computation because it is pointless for exemplifying your case, but let me just highlight that Bellman-Ford-Moore would also perform that evaluation. By the way, it is unclear whether you are considering a directed or undirected graph. I just assumed it is directed: $S\rightarrow B\rightarrow C\rightarrow S$.
  • As noted in the comments by xskxzr, there is no negative cycle in your exmaple. A negative cycle is defined as a path which starts and ends in the same vertex whose overall cost (defined as the sum of all edge costs) is strictly negative. In your case, there is only one cycle from $S$ to it, but it has a cost which is is strictly positive: $c(S, B) + c(B, C) + c(C,S)=1-1+1=1>0$.

I mention these points only to make the answer clearer (if possible) and more useful to other readers.

I will try now to address your question. Once the first phase is over, the distance of the shortest-path from the start vertex $S$ to all other vertices in your graph has been already computed. Let $d_i$ denote the cost of the shortest path from $S$ to the $i$-th vertex.

Consider now any vertex of your graph, $v_i$, and all incident edges to it. Clearly, at least one should be in the shortest-path from $S$, whereas all the others should not. Take any vertex $u$ which has an edge from it to $v_i$:

  • If the edge $\langle u, v_i\rangle$ is part of the optimal path from $S$ to $v_i$ then clearly $d_u + c(u, v_i)=d_{v_i}$
  • Otherwise, $d_u + c(u, v_i)>d_{v_i}$ as this is not part of the optimal path.

Thus, when starting the second phase (for detecting negative cycles), there is at least one edge for each vertex for which equality holds without the presence of negative cycles! This is just a consequence of the definition of shortest-path as shown above. This observation precludes the usage of $\leq$ for detecting cycles, as equality holds without negative cycles.

Let us now consider the case of negative cycles. Their essential property is that they decrease the value of reaching its final vertex indefinitely (as crossing it again would reduce the cost to reach its end vertex), i.e., negative cycles strictly decrease the cost of reaching its end vertex and hence, the only way $d_u + c(u, v_i) < d_{v_i}$ is because there is at least one negative cycle.

In your specific example, make $c(C,S)=-1$. Now you have a negative cycle from $S$ to itself. Clearly, once the first phase is over, the cost of the shortest distances computed by Bellman-Ford-Moore would be: $d_S = -2, d_B = 0, d_C = -1$. I assume the following order of edges: $\langle S, B\rangle$, $\langle B, C\rangle$ and $\langle C, S\rangle$ and recall that the first phase is ran as many times as edges minus 1, i.e., twice in your example. So far, after the first iteration (which considers updating the target vertex of all edges in the order given above) of the first phase $d_S = -1, d_B = 1, d_C = 0$. Because Bellman-Ford-Moore dictates to run the first phase as many times as vertices minus one (the reason beig that the costs computed in the previous iteration should be propagated to the longest path whose number of edges is upper bounded by the number of vertices minus 1), a second iteration of the first phase is conducted and the cost of the shortest-path to all vertices gets decremented again, $d_S = -2, d_B = 0, d_C = -1$.

Next, when running the second phase it turns out that $d_S + c(S,B) = -2 + 1 = -1 < d_B = 0$ which reveals the presence of the negative cycle using $<$.

Hope this helps,

$\endgroup$
  • $\begingroup$ Thank you for a very well thought out answer! Updated my question wordings to use phase instead of iteration. I have one confusion in your answer though. In your last paragraph you wrote "The cost of the shortest distances would be d_{S} = -1. I don't see how the distance to itself would be -2? $\endgroup$ – alex Sep 14 at 15:53
  • $\begingroup$ I edited the last paragraph. The reason is that with a graph with three vertices the first phase shall be ran twice ($|V|-1$) $\endgroup$ – Carlos Linares López Sep 14 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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