There are eight small islands in a lake, and the state wants to build seven brid
ID: 3688427 • Letter: T
Question
There are eight small islands in a lake, and the state wants to build seven bridges to connect them so that each island can be reached from other one via one or more bridges. The cost of constructing a bridge is proportional to its length. The distances between pairs of islands are given in the following table.
1
2
3
4
5
6
7
8
1
-
240
210
340
280
200
345
120
2
-
-
265
175
215
180
185
155
3
-
-
-
260
115
350
435
195
4
-
-
-
-
160
330
295
230
5
-
-
-
-
-
360
400
170
6
-
-
-
-
-
-
175
205
7
-
-
-
-
-
-
-
305
8
-
-
-
-
-
-
-
-
1 240 2
210 155
185
120 180 215 175 265
345 200 280 340
8
195 3
435
350
305 115
260
230
295
7 4
330
160
175 205 170
6 400 5
360
(1). You need to find the seven bridges which costs the least distance. Apply the Prim’s algorithm. The starting island is 1. Show the process of finding the answer. Find the constructed seven bridges and the total cost.
(2). It is found later that the distance between island 1 and island 8 was not 120. It is 222. Apply again Prim’s algorithm to find the result.
1
2
3
4
5
6
7
8
1
-
240
210
340
280
200
345
120
2
-
-
265
175
215
180
185
155
3
-
-
-
260
115
350
435
195
4
-
-
-
-
160
330
295
230
5
-
-
-
-
-
360
400
170
6
-
-
-
-
-
-
175
205
7
-
-
-
-
-
-
-
305
8
-
-
-
-
-
-
-
-
Explanation / Answer
Any more help needed please comment
>Mainly the Prim-Jarník algorithm works by adding a new vertex to the tree at each step.
>order of adding will depend on the starting vertex, although the resulting tree shoul d be the same.
For example, if we choose vertex 8 as the starting vertex, the edges are added in this or der:
So here is the way:
8 to 1 (120)
8 to 2 (155)
8 to 5 (170)
5 to 3 (115)
5 to 4 (160)
2 to 6 (180)
6 to 7 (175)
So finally graph willl be in this way:
1 -- 8 -- 2 -- 6 -- 7
|
|
3 -- 5 -- 4
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.