There are n islands and there are many bridges connecting them. Each bridge has some cost attached to it. We need to find bridges with minimal cost such that all islands are connected.
Answers
What algorithm can be used to solve this problem ?
Edit: What can be used as a brute force approach if the values of N, M are very small, say NxM <= 100?
Example: In the given image, green cells indicate islands, blue cells indicate water and light blue cells indicate the cells on which a bridge should be made. Thus for the following image, the answer will be 17.
Initially I thought of marking all the islands as nodes and connecting every pair of islands by a shortest bridge. Then the problem could be reduced to Minimum spanning tree, but in this approach I missed the case where edges are overlapping. For example, in the following image, the shortest distance between any two islands is 7(marked in yellow), so by using Minimum Spanning Trees the answer would be 14, but the answer should be 11 (marked in light blue).
Hope this helps......♥♥♥♥
Answer:
Step-by-step explanation:
Monk visits the land of Islands. There are a total of N islands numbered from 1 to N. Some pairs of islands are connected to each other by Bidirectional bridges running over water.
Monk hates to cross these bridges as they require a lot of efforts. He is standing at Island #1 and wants to reach the Island #N. Find the minimum the number of bridges that he shall have to cross, if he takes the optimal route.
Input:
First line contains T. T testcases follow.
First line of each test case contains two space-separated integers N, M.
Each of the next M lines contains two space-separated integers X and Y , denoting that there is a bridge between Island X and Island Y.
Output:
Print the answer to each test case in a new line.
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 104
1 ≤ M ≤ 105
1 ≤ X, Y ≤ N
Hope it helps you...