2
$\begingroup$

Define $spdist(s,t)$ as the distance of the shortest path from vertex $s$ to $t$.

Define $IN(v)$ as the set of in-neighbors of $v$.

Define $w(u,v)$ as the weight of the edge $(u,v)$.

I am asked to prove the following two inequalities to gain the correctness of Dijkstra's algorithm:

$$spdist(s,v)\leq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$$

and

$$spdist(s,v)\geq min_{u \in IN(v)} \{spdist(s,u)+w(u,v)\}$$

For the ≤ direction, it is quite obvious. Since we must go through either one of the edge $(u,v)$ to reach $v$, $spdist(s,v)$ is by definition smaller or equal to the RHS.

However, I am having trouble proving the ≥ direction. May I have some intuition of tips on how to prove the ≥ direction?

Thanks!

$\endgroup$
2
$\begingroup$

Consider a shortest path from $s$ to $v$. Let $u \in \mathrm{IN}(v)$ be the vertex preceding $u$ in this shortest path. The path from $s$ to $u$ is also a shortest path, and so $\mathit{spdist}(s,v) = \mathit{spdist}(s,u) + w(u,v)$.

$\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.