"Traffic in winter is often difficult in the high mountains. It is then necessary to determine the most practical routes between any two villages in the geographical region under consideration, in our case the Montagne County.
Hence, at the beginning of the Fall, the representatives of the Montagne County transportation come together to determine which roads must be absolutely kept clear of snow and ice during the coming winter, while the rest of the roads will be blocked to travelers.
Throughout most of the year, the people living in the villages of Montagne County usually travel via the roads that give the shortest routes. However, once the winter approaches, they are not so much concerned about the length of the roads, but rather the altitude, which really determines just how difficult the trip may be. The higher the altitude of a given road,the more difficult it is to travel along that road.
Once the transportation representatives start to determine which roads should be kept clear,the first thing they do is annotate each road e with an altitude value ae, which gives the altitude of the highest point on road e.
Interestingly enough, the altitudes of the roads in Montagne County are such that, no two roads have the same altitude value.
Consider a route P between any two villages x and y. The height of P is defined as the maximum altitude value among all the roads on P. P will be considered winter-optimal if it has the minimum height over all routes from x to y.
The transportation representatives must decide which set of roads, denoted by C, to keep cleaned during winter by satisfying the following two conditions:
• the roads in C must connect any two villages x and y in Montagne County,
• for any two villages x and y, the height of the winter-optimal route determined by the roads in C should be less than or equal to the height of the route determined by the roads during any other non-winter season."
I got this problem in my homework, and I'm thinking to approach it as a version of finding the shortest path, but the more I read the more I get confused, should I write it with Kruskal's algorithm. Any type of hint would be appreciated
This is the minimum bottleneck spanning tree problem. You were on the right track with Kruskal's algorithm.