Moore’s Improvement

Deriving Moore’s algorithm from BFS

Neither Moore nor Bellman described the Bellman-Ford algorithm in the form I’ve presented here. Moore presented his version of the algorithm (“Algorithm D”) in the same paper that proposed breadth-first search (“Algorithm A”) for unweighted graphs; indeed, the two algorithms are nearly identical. Although Moore’s algorithm has the same $O(V E)$ worst-case running time as BellmanFord, it is often significantly faster in practice, intuitively, because it avoids checking edges that are “obviously” not tense.

Moore derived his weighted shortest-path algorithm by making two modifications to the breadth-first search. First, replace each “$+1$” with “$+w(u\rightarrow v)$” in the innermost loop to take the edge weights into account. Second, check whether a vertex is already in the FIFO queue before $Inserting$ it so that the queue always contains at most one copy of each vertex.

Following our earlier analysis of breadth-first search, let’s introduce a token $\maltese$ to break the execution of the algorithm into phases. Just like the breadth-first search, each phase begins when the token is $Pushed$ into the queue and ends when the token is $Pulled$ out of the queue again. Just like BFS, the algorithm ends when the queue contains only the token. The resulting algorithm is shown below.