After reviewing the Bellman-Ford algorithm I can see that it runs with time complexity of $O(n^2)$ or, more exactly, $O(VE)$. It is necessary to loop (V-1) times the number of edges which is in fact 2 nested loops. This is true even if it includes the detection of negative cycles because this task only needs a last loop. However, I have seen that the algorithm time complexity is $O(n^3)$ in some sites. Specifically, the site where I saw it explains 2 steps:
- A graph is built using 2 nested loops.
- Bellman-Ford is applied to detect negative cycles.
Such a site says that $step$ $1$ is $O(n^2)$ (which is logical) and $step$ $2$ is $O(n^3)$
Is this possible? I will very much appreciate your feedback because I cannot find a logical explanation.
Respectfully,
Jorge Maldonado