This is a task from an old exam I'm doing for learning:
Let $G$ be a Digraph with conservative edgeweights $c: E(G) \rightarrow \mathbb{R}$. Let $T$ be a spanning arborescence with root $s$. Proof that the following is equivalent:
- $T$ is a shortest path tree with root $s$ in $G$
- For every edge $(x,y) \in E(G)$ it is: $\text{dist}_T(s,y) \leq \text{dist}_T(s,x) + c((x,y))\quad\quad\quad(I)$
My proof is:
$1. \Rightarrow 2.$ is trivial. So let's proof the other implication.
We have to proof: $\forall y\in V(G): \text{dist}_T(s,y) = \text{dist}_G(s,y) \quad\quad\quad(II)$. Now choose such a $y$.
Assume that $\text{dist}_G(s,y)$ is given by a path $P$ in $G$, i.e.: $\sum_{e \in P(E)}c(e) = \text{dist}_G(s,y)$.
Now we use an inductive argument over the paths length $n = |V(P)|$.
For $n=0$ it's trivial that $(II)$ is true since the distances are $0$.
Now assume it's true for $|V(P)| = n$. Let $|V(P)| = n+1$. We can now simply define $P'$ as $(v_1,...,v_n)$ with $P = (v_1,...,v_{n+1})$ with $v_{n+1} = y$, so we just "take out" the last vertex and also the corresponding edge, let it be $e$. Now we can use the induction on $P'$ and $v_n$ instead of $y$.
Thus, we get $\text{dist}_T(s,v_n) = \text{dist}_G(s,v_n)$. From here, we can simply use $(I)$ and get:
$\text{dist}_T(s,y) \leq \text{dist}_T(s,v_n) + c(e) = \text{dist}_G(s,v_n) + c(e) = \text{dist}_G(s,y)$.
That's all we needed.
Is this correct?
It seems a bit too easy to me. And I'm not using that the weights are conservative. But without using this, we'd have (if there's a negative cycle) a path of length negative infinity. I guess I have to use this in the induction, but the induction seems fine to me though.
