Checking of a graph S is a shortest path tree in G (Algorithm + Correctness)

Question

G is a connected undirected graph with positive weights only. S is the shortest path tree (not necessarily SPT of G). So I am to design an algorithm to check if graph S is the shortest path tree of a graph G.

My algorithm is something like....

Run Dijkstra's algorithm (returning the graph, not the shortest path) on G and S. Check each vertex's dist(v) value and if all are the same, then S is the shortest path tree for G.

I don't know if this algorithm works or not, but I think it is reasonable. If it is true how do I prove its correctness, if not, a counterexample would be very helpful?

* I posted this on CS Exchange as well *

Answer 1

proof by contradiction:

assume S is a shortest path tree of G (with the same root), and that there exists a vertex v where dist(v) from Dijkstra's algorithm does not equal its distance in S.

Lets examine the two options:

1. the dist(v) from Dijkstra's algorithm on G is bigger than its value in S. If so this implies that Dijkstra's algorithm is wrong, since there is a shorter path to this vertex.

2. the dist(v) from Dijkstra's algorithm on G is smaller than its value in S - this means that S could not be a valid shortest path tree, because a shorter path exists to vertex v, thus contradicting our initial assumption.

Q.E.D.