题目

Problem

Figure 3 represents a network of roads between ten villages, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.

(a) Use Dijkstra’s algorithm to find the shortest route from A to J. State the route and its length.

(6)

During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.

(b) Use Prim’s algorithm, starting at A, to find a minimum connector for the five villages A, B, C, D and E. You must clearly state the order in which you select the edges of your minimum connector.

(2)

(c) Use Kruskal’s algorithm to find a minimum connector for the five villages F, G, H, J and K. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.

(2)

(d) Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.

(1)

(Total 11 marks)

题目中文翻译

图 3 表示十个村庄 A、B、C、D、E、F、G、H、J 和 K 之间的道路网络。每条边上的数字表示相应道路的长度（单位：km）。地方议会需要找到从 A 到 J 的最短路线。

(a) 使用 Dijkstra 算法找到从 A 到 J 的最短路线。说明路线及其长度。

冬季期间，议会需要确保即使在大雪天气下，所有十个村庄也能通过道路到达。议会希望最小化需要保持畅通的道路总长度。

(b) 使用 Prim 算法，从 A 开始，找到五个村庄 A、B、C、D 和 E 的最小连接子图。你必须清楚地说明你选择最小连接子图中边的顺序。

(d) 计算议会必须保持道路无雪的总长度，以确保所有十个村庄都能到达。

解答

(a)

思路

使用 Dijkstra 算法。每次從尚未確定的頂點中，選取暫定標號最小者作為下一個確定頂點，再用它更新相鄰頂點的暫定標號。最後從 $J$ 的標號反向追溯，得到由 $A$ 到 $J$ 的最短路線。

答题过程

The labelling table is

Vertex	Working values	Final value	Order of labelling
$A$	$0$	$0$	$1$
$B$	$3$	$3$	$2$
$C$	$8,\ 7$	$7$	$3$
$D$	$12$	$12$	$4$
$E$	$24,\ 22,\ 20$	$20$	$5$
$F$	$41$	$41$	$6$
$G$	$46$	$46$	$7$
$H$	$48$	$48$	$8$
$K$	$72,\ 70$	$70$	$9$
$J$	$88,\ 78,\ 76$	$76$	$10$

Hence the shortest route is

A-B-D-E-F-H-K-J,

and its length is

\boxed{76\text{ km}}.

(b)

思路

從 $A$ 開始使用 Prim 算法：每一步選取一條權值最小、且把目前的樹連到新頂點的邊。注意選邊只比較當時可用的邊，因此選取順序不必按所有邊的權值遞增。

答题过程

Starting at $A$ , Prim’s algorithm selects the edges in the order

AB(3),\quad BC(4),\quad BD(9),\quad DE(8).

Thus the total weight of this minimum connector is

3+4+9+8=24.

(c)

思路

對 $F,G,H,J,K$ 之間的邊使用 Kruskal 算法，按權值由小到大考慮各邊；若加入某條邊會形成迴路，就捨棄該邊。選到四條邊後便已連通五個頂點。

答题过程

Applying Kruskal’s algorithm gives

Edge	Weight	Decision
$FG$	$5$	Select
$JK$	$6$	Select
$FH$	$7$	Select
$GH$	$10$	Reject: it forms a cycle
$HK$	$22$	Select

Therefore the minimum connector contains

FG,\quad JK,\quad FH,\quad HK,

with total weight

5+6+7+22=40.

(d)

思路

把 (b) 和 (c) 的兩棵最小生成樹，用連接兩部分的邊 $EF$ 連起來即可。總長度等於兩棵樹的權值加上 $EF$ 的權值。

答题过程

The two minimum connectors are joined by $EF$ , whose weight is $21$ . Therefore the total length is

24+21+40=\boxed{85\text{ km}}.

IAL 2019 June D1 Q2

题目

解答

(a)

思路

答题过程

(b)

思路

答题过程

(c)

思路

答题过程

(d)

思路

答题过程