. Consider a directed graph G = (N,E) and assume we have a weight function weight:...

 

Transcribed Image Text:

. Consider a directed graph G = (N,E) and assume we have a weight function weight: &→ {1,..., W} with W some maximum integer value W. P4.1. Assume W = 1 (all edges have weight 1). Given node n = N, provide an algorithm that can compute the shortest path from node n to any other node m in ~|N|+|E|. In this case, the shortest path is the path with the fewest edges. P4.2. Given node n € N, provide an algorithm that can compute the shortest path (in terms of the sum of the weights of edges on the path) from node n to any other node m in ~|N|+W|E|. P4.3. Given node n = N. provide an algorithm that can compute the shortest path (in terms of the sum of the weights of edges on the path) from node n to any other node m in ~WIN|+|E|. For each question, explain why your algorithm is correct, why your algorithm achieves the stated complexity, and which graph representation you use. . Consider a directed graph G = (N,E) and assume we have a weight function weight: &→ {1,..., W} with W some maximum integer value W. P4.1. Assume W = 1 (all edges have weight 1). Given node n = N, provide an algorithm that can compute the shortest path from node n to any other node m in ~|N|+|E|. In this case, the shortest path is the path with the fewest edges. P4.2. Given node n € N, provide an algorithm that can compute the shortest path (in terms of the sum of the weights of edges on the path) from node n to any other node m in ~|N|+W|E|. P4.3. Given node n = N. provide an algorithm that can compute the shortest path (in terms of the sum of the weights of edges on the path) from node n to any other node m in ~WIN|+|E|. For each question, explain why your algorithm is correct, why your algorithm achieves the stated complexity, and which graph representation you use.