Moore’s Improvement

Deriving Moore’s algorithm from BFS

Neither Moore nor Bellman described the Bellman-Ford algorithm in the form we’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 $Insert$ing it so that the queue always contains at most one copy of each vertex.

Following our earlier analysis of breadth-first search, we’ll 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 $Push$ed into the queue and ends when the token is $Pull$ed out of the queue again. Just like BFS, the algorithm ends when the queue contains only the token. The resulting algorithm is shown below.