Proving inequalities related to Dijkstra's algorithm

Question

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!

Answer 1

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