Let G = (V,E) be a graph.

And We define n = |V| and e = |E| to simplify your answers.

Each edge has a positive weight. Explain which algorithm you would use, and report its worstcase complexity, in each of the following situations.

By path length, we always mean the sum of the weights on the edges of a path.

a) G is connected and undirected. Find the shortest path from node 1 to node n

b) G is an undirected complete graph. Find the shortest path from node 1 to node n that visits all other nodes.

c) G is directed. Determine if G is a dag

d) G is a tree. Find the longest path in the tree if one endpoint is the root

e) G is a tree. Find the longest path in the tree if one endpoint is the root. (17). G is connected and undirected. Find the shortest path from node 1 to node n if all weights are one