2
$\begingroup$

In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow:

Let u be v's predecessor on a shortest path P:s->...->u->v from s to v. Then, If d(u) = δ(s,u) and edge (u, v) is relaxed, we have d(v) = δ(s,v), where the funciton δ(x, y) denotes the minimum path weight from x to y.

I wonder why we need the condition d(u) = δ(s,u) in this lemma. If Path P: s->...->u->v is a shortest path from s to v, then by the property of optimal substructure, the subpath s->...->u of P must also be a shortest path from s to u. Therefore, d(u) must equal to δ(s,u).

Does there exist the case that d(u) ≠ δ(s,u) but P: s->...->u->v is a shortest from s to v? If it does, can someone offer an example here.

Any help will be appreciated

PS: if you are interested in the entire proof. Check here, the proof starts at 45:30

$\endgroup$
3
$\begingroup$

It looks like you misunderstood the nature of $d(v)$ for a vertex $v$.

$d(v)$ is designed to hold the current known shortest distance from $s$ to $v$ at each step/stage of the algorithm. That is, $d(v)$ is not a fixed value given $s$ and $v$ alone.

At the start of Dijkstra's algorithm, $d(s)$ is initialized to 0 and $d(v)$ is initialized to $\infty$ for each vertex $v\not=s$ in $G$. For example, let graph $G$ have three vertices $s, u, v$ and two edges $\{s,u\}, \{u,v\}$. The path $s,u,v$ is a shortest path from $s$ to $v$. Right right after Dijkstra's algorithm has initialized $d(u)$ to $\infty$, we have $d(u)=\infty\not=1=\delta(s,u)$. This is one of the examples you are looking for. In fact, for all graphs in which $u$ is reachable from $s$, as long as $d(u)$ has not been relaxed to $\delta(s,u)$, we will have, of course, $d(u)\not=\delta(s,u)$.

On the other hand, $d(u)=\delta(s,u)$ must hold at the time when the edge $(u, v)$ is being relaxed in Dijkstra's algorithm. That might be the reason that prompts you to raise this question. Note that as a property of the Dijkstra's algorithm, that fact is not proved yet at the point of time in that lesson.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.