How does a Bellman-Ford with FIFO Queue speed up its iteration?

Question

My lecturer mentions this:

• Try to decrease the running time of one iteration of loop 1: consider only edges which may give effective relax operations.

• A vertex v is active, if the edges outgoing from v have not been relaxed since the last time d[v] has been decreased.

• Perform RELAX only on edges outgoing from active vertices.

• Store active vertices in the Queue data structure.

My question is, how does a FIFO Queue speed up Bellman-Ford's iterations? In what circumstances do you 'enqueue'?

Answer 1

The queue is there only because it is a convenient data-structure to keep track of the active nodes.

You enqueue a node when you first try to relax an edge connected to that node. By the time you reach the node, you will have relaxed all edges from active neighbors onto that node.

Doing those steps transforms the Bellman-Ford algorithm into something closer to Dijksta's algorithm.

---

If node is active, it is next up for consideration. You also have visited nodes, which you already have determined everything you need to know about. And nodes that has not yet been reached is unvisited.

You can think of the three statuses as colors. You start off with just the initial node being colored active, and everything else being unvisited. As you move along, the active color will move outwards forming a border surrounding the visited nodes. You are done when you have no more active nodes, and everything is colored visited.

---

As an alternative to the queue, you could use two lists. The first one contains the active nodes you are currently considering, and any new active nodes you put into the second list. After the first list is exhausted, you empty it, and swap the two lists. Using a single queue instead, you blend the iterations together, by not having a distinct border between the current iteration, and the next.