Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \to R$, and let $s \in V$ be a source vertex. Assume that G does not contain a negative cycle reachable from $s$. Then, if we execute relaxation steps resulting in $d[v] = \delta(s, v)$ for all $v \in V$ . Then the predecessor subgraph $G_\pi$ is a shortest-path tree rooted at $s$.

When proving that the unique path in $G_\pi$ are shortest paths, in CLRS, we assume a path $p = (s = v_0, v_1, . . . ,v_k = v)$ to be a path in $G_π$.

For $i = 1, 2, . . . k$ we have both $d[v_i] = \delta(s, v_i)$ and $d[v_i] \ge d[v_i−1] + w(v_i−1, v_i)$.

How does this inequality hold when proving the correctness of the algorithm that calculates the shortest path tree? Since upon termination and according to the hypothesis, $d[v] = \delta(s, v)$ for all $v \in V$, by the triangle inequality, shouldn't the inequality be$d[v_i] \le d[v_i−1] + w(v_i−1, v_i)$ ?


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.