Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time
Relax every edge of $$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.

Referring to this statement: As in Bellman-Ford, we run the algorithm $|V|-1$ times to compute the single-source shortest path. After this, we run the same algorithm once to check whether any relaxation happened in the graph. If there was any relaxation that means there is a negative weight cycle, and we return False. That's not exactly the case here, however you get the idea! If the algorithm given by the professor was right, then there shouldn't have any room for relaxation because relaxation means that the current shortest path $\mathrm{delta}(s,v)$ is not the shortest ($d(s,v) &gt; \mathrm{delta}(s,u) + w(u,v)$). Hence, the algorithm was wrong.