<p>Here's the algorithm (from the wikipedia page) then a proof of the time bound:</p>
<pre><code> 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) &lt; d(v) then  
   9                d(v) := d(u) + w(u, v)
  10                if v is not in Q then
  11                    push v into Q
</code></pre>
<p><strong>Theorem 1.</strong> <em>Given graph <span class="math-container">$G=(V,E)$</span>, the algorithm runs in time <span class="math-container">$O(\min_T \text{depth}(T)\cdot|E|)$</span>, where <span class="math-container">$T$</span> ranges over the shortest-path trees rooted at <span class="math-container">$s$</span>, and <span class="math-container">$\text{depth}(T)$</span> is the depth of <span class="math-container">$T$</span> (the length of the longest path from <span class="math-container">$s$</span> to any node in <span class="math-container">$V$</span>.  Hence, the time is <span class="math-container">$O(|V|\cdot |E|)$</span>.</em></p>
<p>(Note that same bound <span class="math-container">$O(\min_T \text{depth}(T)\cdot |E|)$</span> also holds for Bellman-Ford.)</p>
<p><em>Proof.</em> We will use the following standard fact about the relaxation operations in the inner loop:</p>
<p><strong>Fact 1.</strong> <em>When an edge <span class="math-container">$(u, v)$</span> is relaxed (in the inner loop), if <span class="math-container">$d(u)$</span> is correct (<span class="math-container">$d(u)=\text{dist}(s, u)$</span>) before the relaxation, and <span class="math-container">$(u, v)$</span> is on any shortest path from <span class="math-container">$s$</span>, then <span class="math-container">$d(v)$</span> is correct (<span class="math-container">$d(v)=\text{dist}(s, v)$</span>) after the relaxation, and remains correct for the remainder of the execution.</em></p>
<p>Now consider any execution of the algorithm.
Partition the iterations into contiguous <em>runs</em>, as follows.
The first run contains only the first iteration, when <span class="math-container">$s$</span> is first popped off the queue, and the neighbors of <span class="math-container">$s$</span> are pushed onto the queue.  In general, for <span class="math-container">$i\ge 2$</span>, the <span class="math-container">$i$</span>th run starts just after run <span class="math-container">$i-1$</span> ends, and consists of those iterations in which the vertices in the queue at the end of run <span class="math-container">$i-1$</span> are popped off the queue.</p>
<p>Consider any shortest path <span class="math-container">$P=(s=v_1, v_2, \ldots,v_\ell)$</span> from <span class="math-container">$s$</span> to some node <span class="math-container">$v_\ell$</span>.  We will argue that the algorithm maintains the following invariant: at the start of each run <span class="math-container">$i$</span>, the distance labels <span class="math-container">$d(v_j)$</span> for <span class="math-container">$j\le \min(\ell, i)$</span> are correct (that is, <span class="math-container">$d(v_j) = \text{dist}(s, v_j)$</span> for <span class="math-container">$j\le \min(\ell,i)$</span>).  The invariant holds at the start of run <span class="math-container">$1$</span> because <span class="math-container">$v_1=s$</span> and <span class="math-container">$d(s)=0$</span> at the start of run <span class="math-container">$1$</span> (by Line 3).  Consider the time at the start of any run <span class="math-container">$i\in[\ell]$</span>.  Assume inductively that the invariant holds now.  We will argue that it will hold at the start of the next run <span class="math-container">$i+1$</span>.  Let <span class="math-container">$v_k$</span> be the first vertex on the path whose distance label is not yet correct (at the start of run <span class="math-container">$i$</span>). (If there is no such vertex, all labels on the path are correct, and the invariant holds.)  So <span class="math-container">$v_{k-1}$</span> is correctly labeled, but <span class="math-container">$v_k$</span> is not.  Because the invariant holds now, we have <span class="math-container">$k\ge i+1$</span>.</p>
<p>Consider the most recent time (before the start of run <span class="math-container">$i$</span>) that <span class="math-container">$v_{k-1}$</span> was added to the queue.  By Fact 1, when <span class="math-container">$v_{k-1}$</span> is later removed from the queue (and the algorithm relaxes edge <span class="math-container">$(v_{k-1}, v_k)$</span>), the distance estimate <span class="math-container">$d(v_k)$</span> of <span class="math-container">$v_k$</span> will become correct.  Since <span class="math-container">$d(v_k)$</span> is not yet correct, it must be that <span class="math-container">$v_{k-1}$</span> is still in the queue (at the start of run <span class="math-container">$i$</span>). By Fact 1, when <span class="math-container">$v_{k-1}$</span> is popped from the queue in run <span class="math-container">$i$</span>, the distance label of vertex <span class="math-container">$v_k$</span> will become correct and at the start of the next run <span class="math-container">$i+1$</span>, the labels on vertices <span class="math-container">$v_1, v_2, \ldots, v_k$</span> will be correct.  Because <span class="math-container">$k\ge i+1$</span>, the invariant will hold at the start of run <span class="math-container">$i+1$</span>.  Inductively, all distance labels along the path <span class="math-container">$P$</span> will be correct by the start of run <span class="math-container">$\ell=|P|$</span>.</p>
<p>This holds for all shortest paths <span class="math-container">$P$</span> from <span class="math-container">$s$</span>, so, for any shortest-path tree <span class="math-container">$T$</span> rooted at <span class="math-container">$s$</span>, by the start of run <span class="math-container">$\text{depth}(T)$</span>, the distance labels of <em>all</em> vertices will be correct, so the algorithm will have at most <span class="math-container">$\text{depth}(T)$</span> runs.</p>
<p>In each run, each vertex <span class="math-container">$u$</span> 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, <em>each vertex <span class="math-container">$u$</span> is popped from the queue at most <span class="math-container">$\text{depth}(T)$</span> times.</em></p>
<p>It follows that each edge <span class="math-container">$(u, v)\in E$</span> is considered in Line 7 at most <span class="math-container">$\text{depth}(T)$</span> times.  It follows that the total number of iterations of the inner loop is at most <span class="math-container">$|E|\cdot \text{depth}(T)$</span>.  This implies the theorem. <span class="math-container">$~~~\Box$</span>.</p>

CC BY-SA 4.0
2022-02-10T16:28:07.257Z
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^*)$?
Maltus
CC BY-SA 4.0
2022-02-10T19:11:24.877Z
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|)$.
Neal Young
CC BY-SA 4.0
2022-02-05T23:46:47.950Z
2022-02-07T03:07:02.217Z
2022-02-07T03:07:02.217Z
Neal Young
<p>I am trying to prove the worst-case asymptotic time complexity of the <a href="https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm" rel="nofollow noreferrer"><em>Shortest Path Faster Algorithm</em> (SPFA)</a>. I know the complexity is the same as the &quot;original&quot; Bellman-Ford (BF) algorithm, that is, <span class="math-container">$O(|V|\cdot |E|)$</span> where <span class="math-container">$V$</span> is the set of vertices and <span class="math-container">$E$</span> the set of edges or arcs in the input graph over which shortest paths from a source <span class="math-container">$s \in V$</span> will be computed to every other node.</p>
<p>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.</p>
<p>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?</p>

CC BY-SA 4.0
2022-02-04T17:07:18.380Z
I can't find the paper anywhere online but you could try asking https://www.reddit.com/r/Scholar/
BlueRaja - Danny Pflughoeft
CC BY-SA 4.0
2022-02-04T18:48:41.140Z
Is this a reference request, or are you just interested in knowing how to prove the bound?
Neal Young
CC BY-SA 4.0
2022-02-05T20:43:23.777Z
@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.
Maltus
<graph-algorithms><shortest-path><proof-complexity><worst-case>
Proof of SPFA's worst-case complexity?
Maltus
# Proof of SPFA's worst-case complexity?

(Asked by: username_0 on 2022-02-04)

I am trying to prove the worst-case asymptotic time complexity of the [*Shortest Path Faster Algorithm* (SPFA)](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm). 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?

**Tags:** graph-algorithms, shortest-path, proof-complexity, worst-case

> **Comments:**
> **username_1**: I can't find the paper anywhere online but you could try asking https://www.reddit.com/r/Scholar/  
> **username_2**: Is this a reference request, or are you just interested in knowing how to prove the bound?  
> **username_0**: @username_2, 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.  

---

## 1 answers

### Answer by username_2 on 2022-02-05. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks a lot @username_2. 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^*)$?  
> **username_2**: 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|)$.  

---

