# Proof of shortest-paths optimality conditions

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.

• You got the directions mixed up. The first part assumes that distTo is the shortest path distances and proves the inequalities. The second part goes in the reverse direction. – Yuval Filmus May 26 '14 at 4:41
• Oh... I misunderstood the directions as you have said. This is rather my English problem... Thanks. – hitochan May 26 '14 at 5:48
• The question is based on misunderstanding English (clarified in the comments), and doesn't thus seem that useful for anyone else other than the OP. – Juho Jul 4 '16 at 15:53