Moore’s Improvement

Explore the different techniques used to implement Moore's algorithm efficiently.

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(VE)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+1” with “+w(uv)+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 InsertingInserting 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 PushedPushed into the queue and ends when the token is PulledPulled out of the queue again. Just like BFS, the algorithm ends when the queue contains only the token. The resulting algorithm is shown below.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy