Your boss gives you a list of n of your company’s facilities (and the distances

Question

Your boss gives you a list of n of your company’s facilities (and the distances between them) which she would like to connect with a special network of roads. You know that: (a) Each facility is a positive integer number of miles away from each other facility. (b) Your boss is sure you don’t need to build any road more than 5 miles in length, so, for each facility, she included a list of all of the neighboring facilities within a 5 mile radius. (c) Each mile of road costs $200, 000.

Give an O(n log*(n)) algorithm to help your boss minimize the cost of your company’s road network.

NOTE: The answer does not need to be coded in any language or pseudocode, just give a step-by-step algorithm in english of how to achieve this so that I may be able to understand it.

Explanation / Answer

Dijktras algorithm is best suitable for minimizing the cost of our company's road network.

steps of Algorithm

in each step of algorithm we are marking one vertex and we won't change our decision :hence the term "greedy" Algorithm.

Main steps

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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