Can Bellman-Ford algorithm handle positive cycles?
I am currently studying the Bellman-Ford algorithm and a doubt popped up. From what I learned the Bellman-Ford algorithm creates the shortest path from its sources, if perhaps there is a negative cycle in the graph it returns true and the algorithm stops, and on the other hand it returns false with the shortest path.
My question is now, does the algorithm avoid the positive cycles in the graph for creating the shortest path or does it just not take them into consideration ( and hence falls into their trap)?
Thanks in advance!
If there is a negative cycle then there is no "shortest" path because you can keep going around the cycle as many times as you like to make a path "shorter" (i.e. lower sum of edge weights). If a graph has a negative cycle then an algorithm might fail by falling into an infinite loop or by returning a path which is not shortest; so therefore we are interested in algorithms which can "detect" negative cycles and not fail in one of those ways.
Bellman–Ford is an example of such an algorithm: if the graph has a negative cycle, then the Bellman–Ford algorithm detects that there is no shortest path (and can report what the negative cycle is). This means the algorithm correctly determines that the problem of finding a shortest path does not have a defined solution for this input, instead of giving a wrong result or failing to terminate.
Positive cycles do not create any similar problem, because the existence of a positive cycle does not imply that there is no shortest path. A solution which goes around a positive cycle arbitrarily many times leads to a longer path (i.e. higher sum of edge weights), not a shorter one. So every shortest path algorithm must handle this case correctly, including Bellman–Ford.
Consider a cycle <a,b,c,a> that contains positive weight. It's obvious that, if we set shortest distance from source to vertex a be edge c to a, then this will contradict with the optimal substructure of shortest path and correctness of Belman-Ford algorithm. So the algorithm evaluate length of positive cycle but doesn't consider it as a shortest path.