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 *
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:
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.
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.