# Can Bellman-Ford run with time-complexity of cubic order

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:

1. A graph is built using 2 nested loops.
2. 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,
• When discussing graph algorithms, we often use $n$ for the number of vertices rather than the input length. – Yuval Filmus Jul 19 '17 at 17:44
• Checking for negative length cycles occurs after edge relaxation (computing shortest path values), in $|E|$ time and is not nested. – fade2black Jul 19 '17 at 17:47
• Relevant: CLRS 3ed chapter 24.1, page 651, The Bellman-Ford Algorithm. Relaxing all the edges to create a SSSP should take $O(VE)$, yes, but then simply checking for negative cycle afterwards will take $O(E)$. Detecting all negative cycles would be another story. – ryan Jul 19 '17 at 17:51