题目

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 的最短路线。说明路线及其长度。

(6)

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

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

(2)

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

(1)

（总分 11 分）

解答

(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

\begin{align*} &\,A-B-D-E\\ &\,\hspace{2pt}-F-H-K-J, \end{align*}

and its length is

\boxed{76\text{ km}}.

(b)

解法一

思路

展开

从 $A$ 开始使用 Prim 算法：每一步选取一条权值最小、且把目前的树连到新顶点的边。注意选边只比较当时可用的边，因此选取顺序不必按所有边的权值递增。

答题过程

展开

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

\begin{align*} &\,AB(3),\quad BC(4),\\ &\,\hspace{2pt}BD(9),\quad DE(8). \end{align*}

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}}.

D1 2019 June Q2

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程