Quiz on Bellman-Ford Algorithm

The Bellman-Ford algorithm can correctly compute single-source shortest paths in graphs that contain negative edge weights, as long as there is no negative-weight cycle reachable from the source.

The time complexity of the Bellman-Ford algorithm on a graph with $|V|$ vertices and $|E|$ edges is $O(|V|^2)$ in the standard implementation.

If, after performing $|V|-1$ relaxation passes, the Bellman-Ford algorithm can still relax at least one edge (i.e., decrease some distance), then a negative-weight cycle that is reachable from the source exists.

Bellman-Ford requires that all edge weights be nonnegative, just like Dijkstra's algorithm.

Bellman-Ford is typically used for single-source shortest paths, but by running it once from each vertex as the source, it can be used to obtain all-pairs shortest paths.

In Bellman-Ford, each relaxation step on an edge $(u, v)$ with weight $w(u, v)$ attempts to update $d[v]$ using the formula $d[v] = \min(d[v], d[u] + w(u, v))$.

Compared to Dijkstra's algorithm with a binary heap, Bellman-Ford is asymptotically faster on sparse graphs with nonnegative edge weights.