0
$\begingroup$

According to my understanding, the Bellman–Ford algorithm can handle cyclic graphs with negative weights. but it cannot have negative cycles. But can it handle zero weight cycles?

$\endgroup$
2
$\begingroup$

Yes. Bellman-Ford can handle graphs with zero-weight cycles; they aren't a problem.

Intuitively, negative-weight cycles are problematic because they can make the notion of "shortest path" ill-defined: there is no shortest path. For instance, suppose we have a cycle from A to A with weight -5, and an edge from A to B with weight 10. Then there is no shortest path from A to B. There's a path with length 10 (go straight there), a path with length 5 (traverse the cycle once, then go there), a path with length 0 (traverse the cycle twice, then go there), a path with length -5, a path with length -10, and so on.

Zero-weight cycles don't cause this problem.

$\endgroup$
  • $\begingroup$ Thanks. One more quick question: there is no any algorithm can find the longest path on cyclic graphs (non-negative weight), since the distance of a path can keep incrementing with the cycles. Am I right? $\endgroup$ – Munichong Jan 13 '17 at 17:14
  • $\begingroup$ @Munichong, yes, that's correct. $\endgroup$ – D.W. Jan 13 '17 at 17:17
  • 1
    $\begingroup$ Just one comment here. It is precisely for these reasons that we usually say "shortest simple path". A path is simple if and only if each vertex in the path appears only once. Now, we have two very interesting open questions in the field defined over cyclic graphs: 1) compute the shortest simple path in the presence of negative cycles; 2) compute the longest simple path in the presence of positive cycles. $\endgroup$ – Carlos Linares López Jan 13 '17 at 23:10

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.