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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
3
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.
-
$\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$ Jan 13 '17 at 17:14
-
-
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$ Jan 13 '17 at 23:10