Problem 4 (8 points) – Graph Algorithms (Shortest Paths and…
Problem 4 (8 points) – Graph Algorithms (Shortest Paths and Dynamic Programming) A highway system connects major cities in a country. Some cities are directly connected through highways Others may be reached via other cities. The distances between cities directly connected highways are known. (1) (1 point) Abstract the highway system as a weighted graph G (nodes and edges) with w (weights); (2) (2 points) Describe (no pseudo code) an efficient algorithm to find the shortest distances from a given city s to all other cities (you can mention some known algorithm in your description if it works). What is the time complexity? (3) (5 points) Dynamic programming technique can be used to find the shortest distances between all pairs of cities: (a) formulate the recurrence relationship of the shortest distances between cities i and j using the shortest distances of sub-structures; (b) write pseudo code to implement the recurrence relationship efficiently; and (c) analyze its complexity.
Read Details