I am struggling with understanding the proof of shortest-paths optimality conditions.
Let $G$ be an edge-weighted digraph.
Then values in $distTo[]$ are the shortest path distances from $s$ iff:
- For each vertex $v$, $distTo[v]$ is the length of some path from $s$ to $v$.
- For each edge $e = v \rightarrow w$, $distTo[w] \le distTo[v] + e.weight()$.
Proof.
- [$\Leftarrow$]necessary
- Suppose that $distTo[w] > distTo[v] + e.weight()$ for some edge $e = v \rightarrow w$.
- Then, $e$ gives a path from $s$ to $w$ (through $v$) of length less than $distTo[w]$.
- [$\Rightarrow$]sufficient
- Suppose that $s = v_{0}\rightarrow v_{1}\rightarrow v_{2}\rightarrow\cdots\rightarrow v_{k} = w$ is a shortest path from $s$ to $w$.
-
Then,
$$\begin{array}{rl} distTo[v_{1}] &\le& distTo[v_{0}] + e_{1}.weight()\\ distTo[v_{2}] &\le& distTo[v_{1}] + e_{2}.weight()\\ &\vdots&\\ distTo[v_{k}] &\le& distTo[v_{k-1}] + e_{k}.weight() \end{array}$$
($e_{i}: i^{th}$ edge on shortest path from $s$ to $w$) -
Add inequalities, simplify, and substitute $distTo[v_{0}] = distTo[s] = 0:$
$$distTo[w] = distTo[v_{k}] \le e_{1}.weight() + e_{2}.weight() +\cdots + e_{k}.weight()$$ ($e_{1}.weight() + e_{2}.weight() +\cdots + e_{k}.weight()$ is weight of shortest path from $s$ to $w$) - Thus, $distTo[w]$ is the weight of shortest path to $w$
QED
I do not understand "sufficient" part, especially,
$$\begin{array}{rl}
distTo[v_{1}] &\le& distTo[v_{0}] + e_{1}.weight()\\
distTo[v_{2}] &\le& distTo[v_{1}] + e_{2}.weight()\\
&\vdots&\\
distTo[v_{k}] &\le& distTo[v_{k-1}] + e_{k}.weight()
\end{array}$$
I thought each $distTo$ element should be equal to the left-hand side since each $e$ is the weight of the edge of the shortest path.
And for the last sentence of page 22, "Thus, $distTo[w]$ is the weight of shortest path to $w$.", isn't this obvious because we know that $distTo[]$ are the shortest path distances from $s$? I even don't understand why this sentence is the conclusion for the proof.
I am really confused so I am glad if anyone can help me understand this process.
distTo
is the shortest path distances and proves the inequalities. The second part goes in the reverse direction. $\endgroup$ – Yuval Filmus May 26 '14 at 4:41