Suppose you are given a weighted, directed graph G = (V,E) with n vertices, and a source s. There are no restrictions on

[answerhappygod]

Suppose you are given a weighted, directed graph G = (V,E) with
n vertices, and a source s. There are no restrictions on the
weights, they can be positive or negative. You are also given for
every vertex v ∈ V the distance from s to v, d[v]. (length of the
shortest s Y v path). Unfortunately, it is possible that some of
the values d[e] are incorrect, and higher than the true distance.
You need to find out whether the given distances are correct. Write
an algorithm that checks in time O(m + n) whether for each v the
true length of the shortest path form s to v is indeed d[v]. The
output is either “correct” or report a vertex for which the
estimated distance is wrong. Note, that the algorithm doesn’t have
to compute the actual correct distance and it only needs to report
one of the incorrect vertices.
Hint: iterate over the vertices to determine whether their
distances are correct. You don’t need to ”trace paths” in some
clever way. One of the homework problems is very relevant here.