Coursera

Week 2

Single-source shortest path

Input: directed graph $G = (V, E)$. Let $m = \mid E\mid, n = \mid V\mid$.

• Each edge has non-negative length $l_e$
• Source vertex $s$

Output: for each $v\in V$, compute $L(v)$ be the length of a shortest path $s-v$ path in $G$.

Assumptions:

1. $v\in V$, exists an $s\to v$ path.
2. Important: $l_e \geq 0\ \forall e\in E$.

Question: doesn’t BFS already compute shortest paths in linear time? Answer: yes, if $l_e = 1$ for every $e$ in $E$.

Question: why not replacing each edge $e$ by directed path of $l_e$ unit length edges? Answer: blows up graph size too much.

Dijkstra’s algorithm

Initialize:
X = {S} // vertices processed so far
A[s] = 0 // shortest path distances
B[s] = empty path // computed shortest path

Main Loop
While X != V: // not iterated through the set of edges
	Among all edges (v, w) in E with v in X, w is not in X, pick the one that minimize A[v] + lvw - call it (v*, w*)
	Add w* to X
	Set A[w*] = A[v*] + l_v*w*
	Set B[w*] = B[v*] join (v*, w*)		

Question: why not reduce computing shortest paths with negative edge lengths to the same problem with nonegative edge length? (by adding large constant to edge lengths)

Problem: doesn’t preserve shortest paths.

Correctness

Theorem (Dijkstra): For every directed graph with non-negative edge lengths, Dijkstra’s algorithm correctly computes all shortest-path distances.

i.e. $A_v = L_v,\ \forall v \in V$

Proof: by induction on the number of iterations. Base case: $A_s = L_s = 0$

Inductive step:

Inductive hypothesis: all previous iterations correct i.e. for all $v\in X, A_v = L_v$ and $B_v$ is a true shortest path $s\to v$ in $G$.

In current iteration: we pick an edge $(v^, w^)$ and we add $w^$ to $X$. We add $B_{w^} = B_{v^} \cup (v^, w^*)$.

Also, $A_{w^} = A_{v^} + l_{v^w^}$

To finish proof: need to show that every $s\to w^$ path has length greater than $L_v^{} + l_{v^w^}$ (and if so, our path is the shortest).

Let $P$ is any $s\to w^$ path. $P$ must has the form of $s\to y\to z .. \to w^$ (not directed). Total length of path $P$ must be at least $A_y + l_{yz}$.

Therefore by Dijkstra’s greedy criterion: $A_{v^*} + l_{v^w^} \leq A_y + l_{yz} \leq$ length $P$.

Implementation and running time

Naive implementation: $\Theta(mn)$

• $(n - 1)$ iterations of while loop
• $\Theta(m)$ works per iteration

Can we do better? Yes

Dijkstra and Heap

Recall: raison d’être of heap = perform Insert, Extract in min $\mathcal{O}(\log{n})$

• Conceptually: a perfectly balanced tree.
• Heap property: at every node, key less than equal children’s keys
• Extract min by swapping up last leaf, bubbling down
• Insert via bubbling up

Also: will need ability to delete from the middle of heap.

Two invariants

1. elements in heaps is vertices of $V-X$
2. for $v \in X$, $key_v$ is the smallest Dijkstra greedy score of an edge $(u, v) \in E$ with $u \in X$ (or $\infty$ if no such edges exists).

Point: by invariants, extract-min yields correct vertex $w^$ to add to $X$ next (and we set $A_{w^}$ to $key_{w^*}$).

To maintain invariant 2: that $\forall v \notin X, key_v =$ smallest Dijkstra greedy score of edge $(u, v)$ with $u \in X$.

When $w$ extracted from heap (i.e. added to $X$)

for each edge $(w, v) \in E$:

• if $v \in V-X$ (i.e. $i^{th}$ heap)
  • delete $v$ from heap
  • recompute $key_v = \min({key_v, A_w + l_{wv}})$

So, number of heap operations is $\mathcal{O}(m + n) = \mathcal{O}(m)$ since the graph is weakly connected. So, running time is $\mathcal{O}(m\log{n})$

Quiz

Question 1

Consider a directed graph with distinct and nonnegative edge lengths and a source vertex $s$. Fix a destination vertex $t$, and assume that the graph contains at least one $s-t$ path. Which of the following statements are true?

Answer:

• The shortest (i.e., minimum-length) $s-t$ path might have as many as $n−1$ edges, where $n$ is the number of vertices.
• There is a shortest $s-t$ path with no repeated vertices (i.e., a “simple” or “loopless” such path).

Question 2

Consider a directed graph $G$ with a source vertex $s$, a destination $t$, and nonnegative edge lengths. Under what conditions is the shortest $s-t$ path guaranteed to be unique?

Answer:

• When all edge lengths are distinct powers of 2.

Question 3

Consider a directed graph $G=(V,E)$ and a source vertex $s$ with the following properties: edges that leave the source vertex $s$ have arbitrary (possibly negative) lengths; all other edge lengths are nonnegative; and there are no edges from any other vertex to the source $s$. Does Dijkstra’s shortest-path algorithm correctly compute shortest-path distances (from $s$) in this graph?

Answer:

• Always

Question 4

Consider a directed graph $G$ and a source vertex $s$. Suppose $G$ has some negative edge lengths but no negative cycles, meaning $G$ does not have a directed cycle in which the sum of the edge lengths is negative. Suppose you run Dijkstra’s algorithm on $G$ (with source $s$). Which of the following statements are true?

Answer:

• Dijkstra’s algorithm always terminates, and in some cases the paths it computes will be the correct shortest paths from $s$ to all other vertices.
• Dijkstra’s algorithm always terminates, but in some cases the paths it computes will not be the shortest paths from $s$ to all other vertices.

Question 5

Consider a directed graph $G$ and a source vertex $s$. Suppose $G$ contains a negative cycle (a directed cycle in which the sum of the edge lengths is negative) and also a path from $s$ to this cycle. Suppose you run Dijkstra’s algorithm on $G$ (with source $s$). Which of the following statements are true?

Answer:

• Dijkstra’s algorithm always terminates, but in some cases the paths it computes will not be the shortest paths from $s$ to all other vertices.