Samanatha123
New member
- Joined
- May 3, 2021
- Messages
- 7
Which graph algorithm would be best to do this problem? Can you do bellman ford? How would you justify the runtime in O(n log n)
A small Italian city is such that all the roads in the city are only one-way. Each road is built between two stone houses. There are n roads in total, and each stone house is connected to at least one road. Many of these old stone houses have been converted to restaurants. You arrive in the city and rent one of the houses for the summer, hoping to enjoy many of the local restaurants. Knowing that when you go out to dinner you often over-eat, you are interested in calculating the shortest-distance home from each restaurant. Provide an algorithm for finding the shortest route home from each restaurant. Justify the runtime of O(n log n).
A small Italian city is such that all the roads in the city are only one-way. Each road is built between two stone houses. There are n roads in total, and each stone house is connected to at least one road. Many of these old stone houses have been converted to restaurants. You arrive in the city and rent one of the houses for the summer, hoping to enjoy many of the local restaurants. Knowing that when you go out to dinner you often over-eat, you are interested in calculating the shortest-distance home from each restaurant. Provide an algorithm for finding the shortest route home from each restaurant. Justify the runtime of O(n log n).