A shortest-path tree is a spanning tree T of a connected, undirected graph G = (V, E) that is rooted at some node v ? V , such that path distance in T from v to any other vertex u ? V is the same as the shortest path distance from v to u in G. That is, it is a spanning tree that preserves the length of the shortest path distance in the original graph from v to all other nodes.

Given a connected, undirected graph G = (V, E) with positive weights d ({u, v}) on each edge, provide an O (|E|)-time algorithm to check whether a given tree T is a shortest-path tree of G.