Assume that you are given a function called dijkstra (G, a) which takes a graph G,...

Transcribed Image Text:

Assume that you are given a function called dijkstra (G, a) which takes a graph G, and a source vertex a as input, then finds the shortest path (distances, dist and parents, par) from a to every other vertex in the graph. Use this function to solve problems #1 Present your solution idea with a pseudocode, accompanying necessary explanation. Problem #1: Optimum meeting place You, and your friend Benji, live in a city which has 50 areas numbered from 1 to 50. Some of the areas are connected by bi-directional roads of various lengths. Your house is in 1 and Benji's is in 50. Both of you want to meet. Now propose an algorithm to choose the meeting point that minimizes the total travel time. In other words, if the meeting area you chose is X, it has the minimum dist(1, X) + dist(50, X) among all possible area choices. Expected complexity: 0(V + E) Assume that you are given a function called dijkstra (G, a) which takes a graph G, and a source vertex a as input, then finds the shortest path (distances, dist and parents, par) from a to every other vertex in the graph. Use this function to solve problems #1 Present your solution idea with a pseudocode, accompanying necessary explanation. Problem #1: Optimum meeting place You, and your friend Benji, live in a city which has 50 areas numbered from 1 to 50. Some of the areas are connected by bi-directional roads of various lengths. Your house is in 1 and Benji's is in 50. Both of you want to meet. Now propose an algorithm to choose the meeting point that minimizes the total travel time. In other words, if the meeting area you chose is X, it has the minimum dist(1, X) + dist(50, X) among all possible area choices. Expected complexity: 0(V + E)

Answer rating: 100% (QA)

Certainly To solve the problem of finding the optimum meeting place with minimum total travel time y... View the full answer