# Proving inequalities related to Dijkstra's algorithm

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!

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