3
$\begingroup$

I am trying to prove the worst-case asymptotic time complexity of the Shortest Path Faster Algorithm (SPFA). I know the complexity is the same as the "original" Bellman-Ford (BF) algorithm, that is, $O(|V|\cdot |E|)$ where $V$ is the set of vertices and $E$ the set of edges or arcs in the input graph over which shortest paths from a source $s \in V$ will be computed to every other node.

However, I am failing to find any literature whatsoever that helps me in proving the complexity of SPFA. The original paper by Moore (1959) is nowhere to be found and every other place simply cites SPFA as an improvement of BF but only prove complexity using the original algorithm, which has a different logic.

Is there anyone here who has tried to prove the complexity of SPFA before? Could you provide any hints as to the logic behind such proof?

$\endgroup$
3
  • $\begingroup$ I can't find the paper anywhere online but you could try asking reddit.com/r/Scholar $\endgroup$ Feb 4 at 17:07
  • $\begingroup$ Is this a reference request, or are you just interested in knowing how to prove the bound? $\endgroup$
    – Neal Young
    Feb 4 at 18:48
  • $\begingroup$ @Neal Young, I want to know how to prove the bound. If you happen to know where I can find the reference that would also be great but not strictly necessary. My greatest doubt is how to approach the proof really. $\endgroup$
    – Maltus
    Feb 5 at 20:43

1 Answer 1

2
$\begingroup$

Here's the algorithm (from the wikipedia page) then a proof of the time bound:

 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        /* `relax' edge (u, v) */
   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

Theorem 1. Given graph $G=(V,E)$, the algorithm runs in time $O(\min_T \text{depth}(T)\cdot|E|)$, where $T$ ranges over the shortest-path trees rooted at $s$, and $\text{depth}(T)$ is the depth of $T$ (the length of the longest path from $s$ to any node in $V$. Hence, the time is $O(|V|\cdot |E|)$.

(Note that same bound $O(\min_T \text{depth}(T)\cdot |E|)$ also holds for Bellman-Ford.)

Proof. We will use the following standard fact about the relaxation operations in the inner loop:

Fact 1. When an edge $(u, v)$ is relaxed (in the inner loop), if $d(u)$ is correct ($d(u)=\text{dist}(s, u)$) before the relaxation, and $(u, v)$ is on any shortest path from $s$, then $d(v)$ is correct ($d(v)=\text{dist}(s, v)$) after the relaxation, and remains correct for the remainder of the execution.

Now consider any execution of the algorithm. Partition the iterations into contiguous runs, as follows. The first run contains only the first iteration, when $s$ is first popped off the queue, and the neighbors of $s$ are pushed onto the queue. In general, for $i\ge 2$, the $i$th run starts just after run $i-1$ ends, and consists of those iterations in which the vertices in the queue at the end of run $i-1$ are popped off the queue.

Consider any shortest path $P=(s=v_1, v_2, \ldots,v_\ell)$ from $s$ to some node $v_\ell$. We will argue that the algorithm maintains the following invariant: at the start of each run $i$, the distance labels $d(v_j)$ for $j\le \min(\ell, i)$ are correct (that is, $d(v_j) = \text{dist}(s, v_j)$ for $j\le \min(\ell,i)$). The invariant holds at the start of run $1$ because $v_1=s$ and $d(s)=0$ at the start of run $1$ (by Line 3). Consider the time at the start of any run $i\in[\ell]$. Assume inductively that the invariant holds now. We will argue that it will hold at the start of the next run $i+1$. Let $v_k$ be the first vertex on the path whose distance label is not yet correct (at the start of run $i$). (If there is no such vertex, all labels on the path are correct, and the invariant holds.) So $v_{k-1}$ is correctly labeled, but $v_k$ is not. Because the invariant holds now, we have $k\ge i+1$.

Consider the most recent time (before the start of run $i$) that $v_{k-1}$ was added to the queue. By Fact 1, when $v_{k-1}$ is later removed from the queue (and the algorithm relaxes edge $(v_{k-1}, v_k)$), the distance estimate $d(v_k)$ of $v_k$ will become correct. Since $d(v_k)$ is not yet correct, it must be that $v_{k-1}$ is still in the queue (at the start of run $i$). By Fact 1, when $v_{k-1}$ is popped from the queue in run $i$, the distance label of vertex $v_k$ will become correct and at the start of the next run $i+1$, the labels on vertices $v_1, v_2, \ldots, v_k$ will be correct. Because $k\ge i+1$, the invariant will hold at the start of run $i+1$. Inductively, all distance labels along the path $P$ will be correct by the start of run $\ell=|P|$.

This holds for all shortest paths $P$ from $s$, so, for any shortest-path tree $T$ rooted at $s$, by the start of run $\text{depth}(T)$, the distance labels of all vertices will be correct, so the algorithm will have at most $\text{depth}(T)$ runs.

In each run, each vertex $u$ is popped from the queue at most once, just because all vertices popped from the queue in a given run were in the queue at the start of the run (and the queue never holds two copies of the same vertex). By this and the previous paragraph, each vertex $u$ is popped from the queue at most $\text{depth}(T)$ times.

It follows that each edge $(u, v)\in E$ is considered in Line 7 at most $\text{depth}(T)$ times. It follows that the total number of iterations of the inner loop is at most $|E|\cdot \text{depth}(T)$. This implies the theorem. $~~~\Box$.

$\endgroup$
2
  • $\begingroup$ Thanks a lot @Neal Young. Would mind answering a follow-up? The number of iterations of the for loop in line 7 is equal to the degree of node $u$, lets denote it $\delta(u)$. Of course, $\delta(u) = O(|E|)$. However, would it be a "tighter" bound to say that the complexity depends on $\delta^* = \max_{u \in V} \delta(u)$ rather than on $|E|$? Or am I saying nonesense? In summary: is it a tighter bound to write $O(|V|\cdot \delta^*)$? $\endgroup$
    – Maltus
    Feb 10 at 16:28
  • $\begingroup$ No, the argument given here wouldn't work to show that bound, and I doubt that bound even holds. Consider the case of a regular graph where all vertices have degree $d$. Your time bound would be $O(d |V|) = O(|E|)$. But the algorithm surely doesn't run in linear time on all (even regular) graphs. Probably you are misunderstanding the analysis here, which just shows that each vertex is popped from the queue at most $|V|$ times, and when $u$ is popped from the queue the inner loop takes $O(d(u))$ time, so the total time is $O(\sum_{u\in V} |V| d(u)) = O(|V| |E|)$. $\endgroup$
    – Neal Young
    Feb 10 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.