题目
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.
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.
(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.
(d) Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.
(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 的最小连接子图。你必须清楚地说明你选择最小连接子图中边的顺序。
(c) 使用 Kruskal 算法找到五个村庄 F、G、H、J 和 K 的最小连接子图。你必须清楚地显示你考虑边的顺序。对于每条边，说明你是否将其包含在你的最小连接子图中。
(d) 计算议会必须保持道路无雪的总长度，以确保所有十个村庄都能到达。