Ch24: Single-Source Shortest Paths

tags: algorithm

• contributed by < TYChan6028 >
• textbook: Introduction to Algorithms, Third Edition

Exercises 24.1

24.1-1 Run the Bellman-Ford algorithm on the directed graph of Figure 24.4, using vertex

$z$ as the source. In each pass, relax edges in the same order as in the figure, and show the

$d$ and

$\pi$ values after each pass. Now, change the weight of edge

$(z,x)$ to 4 and run the algorithm again, using

$s$ as the source.

Order of traverse:

$z\to y\to s\to t\to x$

The graph with

$w(z,x)=4$ and

$s$ as the source can be obtained by using the same process.

24.1-2 Prove Corollary 24.3.

Corollary 24.3
Let

$G=(V,E)$ be a weighted, directed graph with source vertex

$s$ and weight function

$w:E\to \mathbb{R}$, and assume that

$G$ contains no negative-weight cycles that are reachable from s. Then, for each vertex

$v\in V$, there is a path from

$s$ to

$v$ if and only if BELLMAN-FORD terminates with

$v.d<\mathrm{\infty }$ when it is run on

$G$. – textbook, p.653

Proof

We will prove this by contradiction.
Let graph

$G$ be initialized with a call to INITIALIZE- SINGLE-SOURCE, which sets

$s.d=0$ and

$v.d=\mathrm{\infty }$ for

$v\in V-\{s\}$.
At BELLMAN-FORD's termination, assume there exists a

$v.d=\mathrm{\infty }$ on the path

$p=<v_0,v_1,...,v_k>$ from

$s⇝v$, where

$s=v_0$ and

$v=v_k$. Since

$v.d=\delta (s,v)$ for all

$v\in V$ at termination,

$\begin{array}{rcl}v.d& =& \delta (s,v_k)\\ & =& \mathrm{\infty }\\ & \le & \delta (s,v_{k-1})+w(v_{k-1},v_k)\end{array}$

We know

$w(v_{k-1},v_k)\ne \mathrm{\infty }$, so

$\delta (s,v_{k-1})=\mathrm{\infty }$. The same can be said for

$\delta (s,v_{k-1})$ to

$\delta (s,v_1)$, until

$\begin{array}{rcl}\delta (s,v_1)& =& \mathrm{\infty }\\ & \le & \delta (s,v_0)+w(s,v_1)\\ & =& \delta (s,s)+w(s,1)\\ ⟹\delta (s,s)& =& \mathrm{\infty }\end{array}$

This contradicts with

$s.d=0$, which proves there is no path from

$s$ to

$v$ if BELLMAN-FORD terminates with

$v.d=\mathrm{\infty }$.

Exercises 24.2

24.2-1 Run DAG-SHORTEST-PATHS on the directed graph of Figure 24.5, using vertex

$r$ as the source.

24.2-2 Suppose we change line 3 of DAG-SHORTEST-PATHS to read for the first |V| - 1 vertices, taken in topologically sorted order. Show that the procedure would remain correct.

DAG-SHORTEST-PATHS(G,w,s)

topologically sort the vertices of G
INITIALIZE-SINGLE-SOURCE(G,s)
for each vertex u, taken in topologically sorted order
    for each vertex v in G.Adj[u]
        RELAX(u,v,w)

Proof

Let topologically-sorted

$V=<v_1,v_2,...,v_k>$, then

$v_k$ has no child nodes. This shows that there does not exist a

$v_{k+1}$ for which

$\delta (s,v_{k+1})\le \delta (s,v_k)+w(v_k,v_{k+1})$ could relax. Since G.Adj[u]

$=\mathrm{\varnothing }$, the for loop on line 4 would go through 0 iterations. Therefore, it is safe to only consider the first

$|V|-1$ vertices.

Exercises 24.3

24.3-1 Run Dijkstra’s algorithm on the directed graph of Figure 24.2, first using vertex

$s$ as the source and then using vertex

$z$ as the source. In the style of Figure 24.6, show the

$d$ and

$\pi$ values and the vertices in set

$S$ after each iteration of the while loop.

The graph with vertex

$z$ as the source can be obtained by using the same process.

24.3-2 Give a simple example of a directed graph with negative-weight edges for which Dijkstra’s algorithm produces incorrect answers. Why doesn’t the proof of Theorem 24.6 go through when negative-weight edges are allowed?

DIJKSTRA(G,w,s)

INITIALIZE-SINGLE-SOURCE(G,s)
S = empty set
Q = G.V
while Q != empty set
    u = EXTRACT-MIN(Q)
    S = UNION(S,{u})
    for each vertex v in G.Adj[u]
        RELAX(u,v,w)

Below is an example for which Dijkstra's algorithm produces an incorrect answer. The negative-weight edge

$u\to z$ creates a negative cycle

$y\to u\to z\to y$ for which an even smaller weight can always be achieved by traversing the cycle indefinitely.

Theorem 24.6 (Correctness of Dijkstra’s algorithm)
Dijkstra’s algorithm, run on a weighted, directed graph

$G=(V,E)$ with non-negative weight function

$w$ and source

$s$, terminates with

$u.d=\delta (s,u)$ for all vertices

$u\in V$.

Theorem 24.6 proves correctness by showing, for each vertex

$u\in V$,

$u.d=\delta (s,u)$ at the time when

$u$ is added to set

$S$. Once the equality is shown, it relies on the upper-bound property to uphold the equality at all times thereafter. Therefore, the algorithm would terminate with

$u.d=\delta (s,u)$ for all vertices

$u\in S=V$.

The proof of Theorem 24.6 illustrates a shortest path from

$s\stackrel{p_1}{⇝}x\to y\stackrel{p_2}{⇝}u$, on which

$s,x\in S$ and

$y,u\in V-S$. It makes a claim that

$u$ is the first vertex for which

$u.d\ne \delta (s,u)$ when it is added to

$S$, then attempts to disprove this by contradiction.
By proving

$y.d=\delta (s,y)$ and because all edge weights are non-negative, it arrives at the relations

$$\begin{array}{rcl}y.d& =& \delta (s,y)\\ & \le & \delta (s,u)\\ & \le & u.d\end{array}$$
Since

$y,u\in V-S$ and

$u$ is chosen over

$y$ to be next included in set

$S$,

$u.d\le y.d$. Combined with the relation shown above,

$y.d=\delta (s,y)=\delta (s,u)=u.d$, which contradicts its claim and completes the proof.

The reason why the proof of Theorem 24.6 does not go through when negative-weight edges are allowed is because we can no longer make the assumption that

$\delta (s,y)\le \delta (s,u)$.
We know

$y.d=\delta (s,y)\ge u.d$, but if

$\delta (s,y)>\delta (s,u)$ due to a negative-weight edge, it is possible that

1. $y.d=\delta (s,y)=u.d>\delta (s,u)$
2. $\delta (s,y)>u.d=a$ and
   $\delta (s,y)>\delta (s,u)=b$ for which
   $a\ne b$