Suppose that you are an engineer for a road construction company. The company ha

Question

Suppose that you are an engineer for a road construction company. The company has been asked to build a set of streets in a newly developed residential area. Each street requires (costs) a number of days to build, based on its length. Further, the city’s Department of Roads has instructed your company to maintain connectivity among all streets built so far, such that residents can begin moving in and can drive from one end of a street to another street, to cover as much as possible of the residential area. Initially, your company has been asked to come up with the fastest “build schedule” that connects the most junctions/intersections/dead ends first. Assume that your company can build only one road at any given time. Assume also that your company has been given a map that shows all of the streets, how they connect to each other, and what their lengths are.
1. Name the algorithm that solves the above problem, and describe how it could be applied to do so.
2. Name another algorithm that could also solve the above problem.
3. Which of these two algorithms is more appropriate for solving the problem? Explain why.

Explanation / Answer

If we talk about optimal cost for construction Dijkshtra's algorithm is best suited algorithm for the given scenario.

It picks the low cost street based on the length of the street and then continues with rest one after other streets following the same procedure covering all the streets one at a time and saves price as well.

And also as far as my knowledge I have two greedy algorithms to solve the given problem.

This road construction can be done based on the minimal spanning tree concept

This given case is example of travelling salesman problem in which a salesman has to visit each and every city only once in his entire journey visiting all the cities. Here also same case

1)prim's algorithm

2)krushkal algorithm

Both are based on minimal spanning tree and similar to Dijkshtra's algorithm

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.