CS student here struggling with this one problem. Graphs are not really my forte, so I would really appreciate any help or proofs.
Let $G = (V, E)$ be a digraph, $a : E → R+$ a weight function defined on its arcs, and $x_0 ∈ V$ from wich any other vertex in $G$ is accessible. An $SP-tree$ for the triple $(G, a, x_0)$ is a directed rooted tree of $G$, $T = (V, E' )$ such that the cost of the path from $x_0$ to u in $T$ is the cost of the shortest path from $x_0$ to u in $G$, for every $u ∈ V$.
(a) Prove that an $SP-tree$ always exists.
(b) Devise an algorithm that finds an $SP-tree$.