申論題

2. A weighted graph G=(V, E) is an undirected graph with nonnegative weight assigned to each edge in E. The length of a path in G is the sum of edge weights of the edges in the path. A path P from vertex u to vertex v is said to be shortest if the length of P is smallest for all paths from vertex u to vertex v.

(B) (13%) Now you a are given a a weighted graph G-(V, E), a specified vertex s in V, an array d ] of size V, and it is claimed that for each v in Y, dty is the length of the shortest path from s to v. The claim may be correct or may be not. Design a linear time algorithm to check whether the claim is correct. Analyses the time complexity of your algorithm and make sure it is linear, that is, the running time of your algorithm must be O(|V|+|E|).