Prove that if a quasi-connected, directed graph with root \(v_{0}\) and positive costs is input to Dijkstra's algorithm (see Exercise 14), then for each \(v eq v_{0}\), a shortest path from \(v_{0}\) to \(v\) is returned. (Hint: Show inductively on the number of vertices added to \(S\) that the path found by Dijkstra to each vertex in \(S\) is the shortest possible.