2
$\begingroup$

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,
Jorge Maldonado

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ On which site did you see? $\endgroup$ – fade2black Jul 19 '17 at 17:42
  • $\begingroup$ When discussing graph algorithms, we often use $n$ for the number of vertices rather than the input length. $\endgroup$ – Yuval Filmus Jul 19 '17 at 17:44
  • $\begingroup$ Bellman-Ford loops on all egdes while looping on all vertices, complexity is Obviously O(VE). But in some cases, for example complete graphs, E = O(V²) as any vertex is connected to all other vertices Bellman-Ford will run in O(V^3) time. $\endgroup$ – Noctisdark Jul 19 '17 at 17:45
  • $\begingroup$ Checking for negative length cycles occurs after edge relaxation (computing shortest path values), in $|E|$ time and is not nested. $\endgroup$ – fade2black Jul 19 '17 at 17:47
  • $\begingroup$ 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. $\endgroup$ – ryan Jul 19 '17 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.