Arguably, one of the best things to do in America is take a great American road...

 

Transcribed Image Text:

Arguably, one of the best things to do in America is take a great American road trip. And in America there are some amazing roads to drive on (think Pacific Crest Highway, Route 66, etc). An intrepid traveller has chosen to set course across America in search of some amazing driving. What is the length of the shortest path that hits at least k of these amazing roads? Assume, that the roads in America can be expressed as a directed weighted graph G = (V, E, d) and that our traveller wishes to drive across at least k roads from the subset RCE of 'amazing' roads. Furthmore, assume that the traveller starts and ends at her home h € V. Also, you can assume that the traveller is OK with repeating roads from R i.e. the k roads she chooses from R do not need to be unique. = |R|. Provide a 4 part solution with runtime in terms of n = |V, m = |E|, k, and r = Hint: First try out k = 1. How can G be modified so that we can use a 'common' algorithm to solve the problem? Arguably, one of the best things to do in America is take a great American road trip. And in America there are some amazing roads to drive on (think Pacific Crest Highway, Route 66, etc). An intrepid traveller has chosen to set course across America in search of some amazing driving. What is the length of the shortest path that hits at least k of these amazing roads? Assume, that the roads in America can be expressed as a directed weighted graph G = (V, E, d) and that our traveller wishes to drive across at least k roads from the subset RCE of 'amazing' roads. Furthmore, assume that the traveller starts and ends at her home h € V. Also, you can assume that the traveller is OK with repeating roads from R i.e. the k roads she chooses from R do not need to be unique. = |R|. Provide a 4 part solution with runtime in terms of n = |V, m = |E|, k, and r = Hint: First try out k = 1. How can G be modified so that we can use a 'common' algorithm to solve the problem?

Answer rating: 100% (QA)

What is the length of the shortest path that hits at least k of these amazing roads ANSWER The shortest path that hits at least k of these amazing roa... View the full answer