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 $Inserting$ 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 $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.

$$\begin{gathered} \underset{‾}{Moore(s):} \\ InitSSSP(s) \\ Push(s) \\ Push(\mathrm{✠})<<startthefirstphase>> \\ whilethequeuecontainsatleastonevertex \\ u\leftarrow Pull() \\ ifu=\mathrm{✠} \\ Push(\mathrm{✠}) \end{gathered}$$ ...