Shortest path:

(a) You are given a strongly connected directed graph G = (V, E) with positive edge weights along with a particular node V . Describe an O((|V | + |E|) lg |V |) time algorithm for finding shortest paths between all pairs of nodes, with the restriction that these paths must all pass through .

(b) Consider a weighted directed graph G = (V,E), where the edge weights are all positive integers, between 1 and c (a constant). Present an O(|V | + |E|) time algorithm to solve the single-source shortest paths problem on this graph. (Hint: dont use Dijkstra. You may need to introduce pseudo-nodes to the graph.)