a s b c t 2 1 1 2 1 6 4

Given a graph $G=(E,V)$ and a source node $s$. Dijkstra finds the shortest weighted path from $s$ to every other node in the graph. The graph however needs to only have non-negative edge weights. In the above graph the shortest path between nodes $s$ and $t$ is $s \rightarrow a \rightarrow b \rightarrow t$. Dikstra is extremely fast. It can run in amortized time $O(n\log(n) + m)$ if we implement Dijkstra with a fiponacci heap.

Example

How does Dijkstra work? Using the above example, we maintain a set of not-sure nodes ${a, b, c, t, s}$. We let $d[v]$ be the current distance from $s$ to $v$. Initially we let $d[v] = \infty$ for any node in not-sure and $d[s] = 0$ for the source node only.

In the first iteration of Dijkstra, we extract the node with the minimum distance in the not-sure list. This node is $s$. We then update the distance of each neighbor based on the following,

$$ \begin{align*} d[u] &= min(d[u], d[u]+weight(s,u)) \end{align*} $$

After updating each neightbor, we mark $s$ as sure. We should see the following values after this iteration.

Iteration s a b c t
0 (extract $s$) 0 2 $\infty$ 1 $\infty$

Iteration 1
We extract the node with the minimum distance again from the not-sure list. This time we extract $c$. We update all the neighbors and at the end of this iteration, we mark $c$ as sure.

Iteration s a b c t
0 (extract $s$) 0 2 $\infty$ 1 $\infty$
1 (extract $c$) 0 2 5 1 7

Final iteration
We continue the same process. We extract the node $a$ and update its neighbors. We then mark it as sure, meaning that the distance from node $s$ to node $a$ is 2 and will not change again. We next extract $b$ and update the neighbors again. We then mark $b$ as sure. We finally extract $t$ which has no out-going edges. At the end of the algorithm, we see that we generated all the shortest paths from $s$ to all the other nodes in the graph.

Iteration s a b c t
0 (extract $s$) 0 2 $\infty$ 1 $\infty$
1 (extract $c$) 0 2 5 1 7
2 (extract $a$) 0 2 4 1 7
3 (extract $b$) 0 2 4 1 5
4 (extract $t$) 0 2 4 1 5


Pseudocode

Set all vertices to not-sure
d[v] = infinity for all v in V
d[s] = 0
while there are not-sure nodes {
	pick the not-sure node u with the smallest estimate d[u].
	for each neighbor v of u {
		if (d[v] < d[u] + weight(u,v)) {
			// It is cheaper to reach v from u than the current path
			d[v] = d[u] + weight(u,v)
		}
	}
	Mark u as sure
	// at this point we know that d[u] = distance(s,v) (proof below)
}

Extracting the path

To reconstruct the actuall path take, we just maintain a pointer to the parent node. We simply keep an additional array $p$ and modify the update step as follows: 

p[v] = -1 for all v in V
while there are not-sure nodes {
	if (d[v] < d[u] + weight(u,v)) {
		// we maintain a parent link
		p[v] = u
	}
}

Full Implementation on Github

Proof of Correctness

Why does Dijkstra work? We need to prove two important claims in order to prove that Dijkstra is correct.

Claim 1: For all $v$, $d[v] \geq d(s,v)$. That is, $d[v]$ will never be an underestimate for any node $v$.

Proof:
Inducive Hypothesis: After $t$ iterations, $d[v] \geq d(s,v)$ for all $v$.

Base Case: After 0 iterations, the algorithms sets $d[s]= 0 = d(s,s)$ and sets $d[v]$ to $\infty$ for all $v \neq s$ and therefore we have $d[v] \geq d(s,v)$, as required.

Inductive Step: Assume that after $t$ iterations, $d[v] \geq d(s,v)$ for all $v$. We will prove the inequality holds after $t+1$ iterations. At iteration $t+1$, we pick the minimum not-sure node $u$ and then update all neighbors $v$ such that: $d[v] = min(d[v], d[u]+w(u,v))$. To see that $d[v] \geq d(s,v)$, notice that:
(1) $d[v] \geq d(s,v)$ by the inductive hypothesis.
(2) $d[u] + w(u,v) \geq d(s,v)$. This is because we know that $d(s,v) \leq d(s,u) + d(u,v)$ and we also know that $d[u] \geq d(s,u)$ by the inductive hypothesis. Therefore, $d(s,v) \leq d[u] + d(u,v)$.

Conclusion: After the algorithm terminates, we have $d[v] \geq d(s,v)$ for all $v$ in $V$, as required. $\blacksquare$

Claim 2: When a vertex $u$ is marked sure, $d[u] = d(s,u)$

Proof:
Inducive Hypothesis: When the t’th vertex $v$ is marked as sure, $d[v] = d(s,v)$.

Base Case: When the first vertex $s$ is marked sure, we know that $d[s]=0=d(s,s)$, as required.

Inductive Step: Suppose we’re about to mark vertex $u$ as sure, and assume every vertex already marked as sure has $d[v]=d(s,v)$. We will show that $d[u]=d(s,u)$. Consider a shortest path from $s$ to $u$.

s z z' u

We want to prove that $d[u]=d(s,u)$. Suppose toward a contradiction that our claim is not true and that $u$ has the wrong estimate. Also suppose that node $z$ is the last node with a correct estimate before node $u$ and that vertex $z’$ is the vertex after $z$ in the shortest path above. We can see that

$$ d[z] = d(s,z) \leq d(s,u) \leq d[u] $$

This is because we assumed $z$ has a correct estimate and we also know that $d(s,z) \leq d(s,u)$ because first, sub-paths of shortest paths are shortest paths (can be proved by contradiction). Second, the distance from $z$ to $u$ is non-negative because all edges have non-negative weights and therefore $d(s,z) \leq d(s,u)$. The last part $d(s,u) \leq d[u]$ follows from claim 1!

So now, we have $d[z] \leq d[u]$. There are two cases:
Case 1: If $d[z] = d[u]$. In this case, since we assumed $z$ has a correct estimate then $u$ must have a correct estimate and we’re done!
Case 2: If $d[z] < d[u]$. In this case, since $u$ was the smallest not-sure node, then $z$ must be sure. Otherwise we would have picked $z$ as the smallest not-sure node. Since $z$ is sure then we must have updated $z$’s neighbors. In particular, we know that $z’$ comes after $z$ so,

$$ \begin{align*} d[z'] &\leq d[z] + w(z,z') \\ &= d(s,z) + w(z,z') \ \ \text{This is because } z \text{ is a sure node so by IH } d[z] = d(s,z) \\ &= d(s,z') \ \ \text{ Subpaths of shortest paths are shortest paths} \\ &\leq d[z'] \ \ \text{ By claim 1} \end{align*} $$

This means that $z’$ has a correct estimate. This is a contradiction because we assumed that $z$ is the last node with a good estimate and therefore, $u$ must have the correct estimate, as required.

Conclusion: After the last node is marked sure, we have $d[v] = d(s,v)$ for all $v$ in $V$, as we wanted to show. $\blacksquare$

Running Time

What are we doing in this algorithm? For each vertex in the not-sure list, we
(1) find the minimum vertex.
(2) remove that vertex.
(3) update all neighbors with lower estimates if possible.

Therefore we see that if we have $n$ vertices and $m$ edges:

$$ \begin{align*} TotalTime &= \sum_{u \in V} \big\{ T(findMin) + \big(\sum_{v \in u.neighbors} T(updateKey)\big) + T(removeMin) \big\} \\ &= n(T(findMin) + T(removeMin)) + m(T(updateKey)) \end{align*} $$

Now it is clear that it really depends on how we implement the list that holds the not-sure nodes. Let’s consider different data structures

  • Arrays
    • findMin will run in $O(n)$
    • RemoveMin will run in $O(n)$
    • UpdateKey will run in $O(1)$
      Therefore, the total time will be $O(n(2n) + m) = O(n^2 + m) = O(n^2)$
  • Red Black Tree
    • findMin will run in $O(\log(n))$
    • RemoveMin will run in $O(\log(n))$
    • UpdateKey will run in $O(\log(n))$
      Therefore, the total time will be $O(n\log(n) + m\log(n)) = O((n+m)\log(n))$.
      Notice here, if the graph is dense, meaning that $m=O(n^2)$, then this is worse than arrays! if it’s sparse, then it’s better.
  • Fibonacci Heaps
    • findMin will run in $O(1)$, amortized time.
    • RemoveMin will run in $O(\log(n))$, amortized time.
    • UpdateKey will run in $O(1)$, amortized time.
      Therefore, the total time will be $O(n\log(n) + m)$, amortized time.

Handling Negative Weights

TODO!!

References

CS161 Stanford