0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 26 '14 at 4:41
  • $\begingroup$ Oh... I misunderstood the directions as you have said. This is rather my English problem... Thanks. $\endgroup$ – hitochan May 26 '14 at 5:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Juho Jul 4 '16 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.