Let G = (N,A) be an undirected graph. (a) Suppose the arcs of G have with...

Transcribed Image Text:

Let G = (N,A) be an undirected graph. (a) Suppose the arcs of G have with nonnegative weights. Explain how you could modify Dijkstra's algorithm (not G) to find a shortest path from a designated node s to all other nodes. (b) (Unrelated to part (a).) Given two designated nodes u and v, construct an O(m) algorithm to determine whether G has a cycle that passes through both u and v. Let G = (N,A) be an undirected graph. (a) Suppose the arcs of G have with nonnegative weights. Explain how you could modify Dijkstra's algorithm (not G) to find a shortest path from a designated node s to all other nodes. (b) (Unrelated to part (a).) Given two designated nodes u and v, construct an O(m) algorithm to determine whether G has a cycle that passes through both u and v.