In SPFA Shortest Path Faster Algorithm why does it have to check if current vertex is in queue before adding it to queue?

Question

procedure Shortest-Path-Faster-Algorithm(G, s)
  1    for each vertex v ≠ s in V(G)
  2        d(v) := ∞
  3    d(s) := 0
  4    push s into Q
  5    while Q is not empty do
  6        u := poll Q
  7        for each edge (u, v) in E(G) do
  8            if d(u) + w(u, v) < d(v) then
  9                d(v) := d(u) + w(u, v)
 10                if v is not in Q then
 11                    push v into Q

In line 10, it checks if v is in Q. Why do we need this step?

Answer 1

When a node gets updated more than once in one iteration, we only need to process it once in the next iteration of the algorithm.

For example, let's say we have three nodes a,b,c and two edges a->c with weight 5 and b->c with weight 2, let the current distnaces be d[a] = 5, d[b] = 6, d[c] = infinity. When we process the edge a->c, the value of d[c] gets updated with 5 + 5 = 10, and pushed into the queue. Then when we process edge b->c the new value of d[c] is 6 + 2 = 8 which is less than current d[c] = 10 so d[c] = 8 now, but c is already in the queue so there is no need to push it again, and the older value of d[c] = 10 is not required anymore in the next iteration.

Answer 2

Intuitively, you can think of SPFA as a variation on the Bellman-Ford algorithm. As a reminder, Bellman-Ford works like this. Here, d[v] denotes our current guess of the distance from the start node s to node v, and dist(u, v) denotes the length of edge (u, v):

set d[v] = infinity for all nodes v
set d[s] = 0

for l = 1 to n-1, where n is the number of nodes:
   for each node u:
       for each node v adjacent to u:
           if d[u] + dist(u, v) < d[v]:
               set d[v] = d[u] + dist(u, v)

The idea is that the loop on l guarantees that at the start of iteration l, the value of d[v] is the length of the shortest path from s to v using at most l edges.

The optimization SPFA uses works by noticing that the inner loop on u will not have any effect unless d[u] changed in the previous iteration of the outer loop. We therefore can save some work by rewriting Bellman-Ford as follows:

set d[v] = infinity for all nodes v
set d[s] = 0

for l = 1 to n-1, where n is the number of nodes:
   for each node u where d[u] changed:
       for each node v adjacent to u:
           if d[u] + dist(u, v) < d[v]:
               set d[v] = d[u] + dist(u, v)

Now, how should we implement this idea? To loop over all nodes that were updated on the previous iteration, and no others, we can maintain a queue containing the nodes we need to process on the next iteration. That queue shouldn’t contain any duplicates, since we just need to know whether we do or don’t process it next time. That gives this code:

set d[v] = infinity for all nodes v
set d[s] = 0
set q = {s}

for l = 1 to n-1, where n is the number of nodes:
   set q’ = {}
   for each node u in q:
       for each node v adjacent to u:
           if d[u] + dist(u, v) < d[v]:
               set d[v] = d[u] + dist(u, v)
               add v to q’ if it’s not already there
   set q = q’

The last step to make this look like the final version of SPFA is to unify the roles of q’ and q. We can do that under the assumption that there are no negative cycles as follows:

set d[v] = infinity for all nodes v
set d[s] = 0
set q = {s}

while q isn’t empty;
    remove a node u from q
    for each node v adjacent to u:
        if d[u] + dist(u, v) < d[v]:
            set d[v] = d[u] + dist(u, v)
            add v to q if it’s not already there