(a) ( 14 points) SSSP validation: Let G = (V, E) be a directed graph with positive edge weighis, aul lei s be an arbitrary vertx of . Your rmmate claius io have writicu a program which computes the single source shortest path tree from s. Specifically, for every vertex u ? V, your roommate tells you the pred(v) and dist (v) values output by Unfortunately, your roommate is not that reliable and so you want to check their solution. Give anl O(V+E) time algorithm to check whether the given For simplicity you can assume that all vertices in the graph are reachable from s, and hence for every vertex in your roommates solution dist(v) oo, and moreover s is the only vertex such that pred(s)NULL (a) ( 14 points) SSSP validation: Let G = (V, E) be a directed graph with positive edge weighis, aul lei s be an arbitrary vertx of . Your rmmate claius io have writicu a program which computes the single source shortest path tree from s. Specifically, for every vertex u ? V, your roommate tells you the pred(v) and dist (v) values output by Unfortunately, your roommate is not that reliable and so you want to check their solution. Give anl O(V+E) time algorithm to check whether the given For simplicity you can assume that all vertices in the graph are reachable from s, and hence for every vertex in your roommates solution dist(v) oo, and moreover s is the only vertex such that pred(s)NULL