Check if T is the shortest path tree rooted at s

Question

I have this issue of which I have been thinking of for a while. It states as follows:

Given a weighted directed graph G(V, E) (non-negative edge weights), a vertex s ∈ V and a spanning tree T(V, E') of G where E' ⊆ E, rooted at s. Design a linear time (linear in the number of vertices and edges) algorithm that checks if T is the shortest path tree of G, rooted at s.

I couldn't come up with any solution that is in linear time, so thought to ask here.

My solution was the following:

In order to determine if a spanning tree T(V, E’) of G rooted at s, where G is a directed weighted graph with vertex set V and edge set E, and E’ ⊆ E, is the shortest path tree of G, we will proceed as follows:

1. Since T is a spanning tree of G, it contains all the vertices, so we can safely add all the edges from G to T such that e ∈ E, e ∉ E’ (i.e. edge e is not in T, but G).
2. Now, we will colour the added edges e.g. with black. This will help us determine if a path from s to any vertex v has passed through edge that is not in T.
3. We will need to precompute the shortest distance from s to any other vertex v in G. Since weights of edges are non-negative, we can use Dijkstra’s algorithm, which will run in O(V^2), or by iterating the topological sort of the tree and relax each adjacent vertices, which will take O(V+E). In this case, we will use the second approach, because it runs in linear time.
4. Therefore, we have to check whether d(u), which is the distance from root s to any vertex u, for every black edge of length l between two nodes u and v, we have d(v) ≤ d(u) + l. The part that compares edges runs in O(E), since it needs to check every edge. Overall, as we need to precompute distances from root s to any other vertex v, the algorithm will take O(E + V).