Bellman-Ford variation

Question

I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax.

//Queue Q; source s; vertices u, v; distance to v d(v)
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q !empty) {
  u ← Dequeue(Q)
  for each neighbor v of u {
    Relax(u, v)
    if d(v) was updated by Relax and v not in Q
      Enqueue(v)
  }
}

But, can anyone explain why this improved version correctly finds the shortest path from $s$ to every other vertex in a directed graph with no negative cycles?

Also, what is the worst-case runtime if every shortest path uses at most $v$ edges?

Answer 1

This is precisely Moore's 1957 formulation of what is now more commonly known as the Bellman-Ford algorithm.

Why does it work?

Moore's algorithm is a special case of Ford's more general relaxation strategy for computing single-source shortest paths:

while any edge is tense
    relax any tense edge

This generic algorithm will always halt after a finite number of relaxation steps with a shortest path tree, unless some negative-weight cycle is reachable from the source vertex (in which case, there is always at least one tense edge, so the algorithm will never halt).

For Moore's algorithm, it is not hard to the following observation by induction:

Every tense edge leaves a vertex that is in the queue.

If fact, this lemma holds if we replace the queue with any other data structure that supports the operations "insert this" and "give me something". (For example, using a priority queue gives us Dijkstra's algorithm!) The algorithm halts when the data structure is empty. Thus, by the previous lemma, when the algorithm halts, there are no tense edges, so we have a shortest-path tree.

What is the running time?

We can naturally divide the execution of the algorithm into phases by adding an artificial token to the queue immediately after the source vertex, just before the main loop begins. Each phase ends when we dequeue the token; if the queue is not empty, we enqueue the token again and start the next phase. If the queue is empty after we dequeue the token, the algorithm ends.

Each vertex in the graph is dequeued at most once in any phase. (Here I'm assuming that enqueuing a vertex that is already in the queue does not actually change the queue.) Thus, each edge in the graph is relaxed at most one in any phase. So each phase runs in $O(m)$ time.

Let $dist_i(v)$ denote the distance value stored in vertex $v$ after $i$ phases. Initially, we have $dist_0(s) = 0$ and $dist_0(v) = \infty$ for all $v\ne s$. It is easy to prove by induction that

$dist_i(v)$ is at most the length of the shortest walk from $s$ to $v$ that uses at most $i$ edges.

This lemma immediately implies that the algorithm ends after at most $n-1$ phases (unless there is a negative cycle). So altogether the algorithm runs in $O(mn)$ time.

For more details, see my lecture notes, or better yet, Bob Tarjan's excellent monograph Data Structures and Network Algorithms. I believe Tarjan was the first to observe that Moore's algorithm is equivalent to Bellman-Ford.