题目
The network shown in Figure 1 represents the paths between nine attractions in a theme park. The number on each edge is the length, in metres, of the corresponding path.
[The total weight of the network is 1960 m]
(a) (i) Use Dijkstra’s algorithm to find the shortest path from A to J.
(ii) State the length of the shortest path from A to J in metres.
Sarita needs to inspect the paths between the attractions. She must travel along each path at least once.
Sarita decides to start and finish her inspection route at A. She wishes to minimise the length of her route.
(b) By considering the pairings of all relevant nodes, find the length of Sarita’s route.
Sarita now decides to start her inspection route at A, but finish at a different attraction. She must still minimise the length of her route and travel along each path at least once.
(c) (i) Determine where Sarita should finish her route. You must justify your answer.
(ii) Calculate the difference between the lengths of the two inspection routes.
题目中文翻译
图 1 表示主题公园中九个景点之间的路径网络。每条边上的数字是对应路径的长度（单位：米）。
[网络总长度为 1960 m]
(a) (i) 使用 Dijkstra 算法求从 A 到 J 的最短路径。
(ii) 说明从 A 到 J 的最短路径长度（米）。
Sarita 需要检查景点之间的路径。她必须每条路径至少经过一次。
Sarita 决定从 A 出发并回到 A。她希望最小化路线长度。
(b) 通过考虑所有相关节点的配对，求 Sarita 路线的长度。
Sarita 现在决定从 A 出发，但在不同景点结束。她仍然必须最小化路线长度且每条路径至少经过一次。
(c) (i) 确定 Sarita 应在哪里结束路线。必须说明理由。
(ii) 计算两条检查路线长度之差。
解答
(a)(i)
解法一
思路
展开
从 A 的永久标号 0 开始，每次选择当前最小的临时标号作为下一个永久标号，再通过该节点更新所有相邻节点。工作值必须按产生顺序保留；J 获得永久标号后，从 J 沿产生最终值的前驱反向追踪路线。
答题过程
展开
Applying Dijkstra’s algorithm from A gives
| Vertex | Order of labelling | Working values | Final value |
|---|---|---|---|
| A | 1 | 0 | 0 |
| D | 2 | 56 | 56 |
| B | 3 | 70 | 70 |
| C | 4 | 182, 154, 147 | 147 |
| E | 5 | 231, 161 | 161 |
| H | 6 | 210, 203 | 203 |
| F | 7 | 217, 245 | 217 |
| G | 8 | 294, 287, 273 | 273 |
| J | 9 | 427, 420, 357 | 357 |
Backtracking from J through the vertices that produced its final label gives the shortest path
(a)(ii)
解法一
思路
展开
J 的永久标号就是从 A 到 J 的最短距离，也可把最短路径 ABFGJ 上的四条边相加进行核对。
答题过程
展开
The length of the shortest path is
(b)
解法一
思路
展开
原网络的奇数度节点为 A、C、E、J。闭合路线必须把它们两两配对，并重复连接每一对的最短路径。列出三种不同配对，选择附加长度最小的一种，再加到网络总长度 1960 m 上。
答题过程
展开
The odd vertices are A, C, E and J. The three possible pairings are
| Pairing | Repeated length (m) | Total (m) |
|---|---|---|
| AC and EJ | 357 | |
| AE and CJ | 525 | |
| AJ and CE | 525 |
The smallest additional length is 357 m. Therefore, the minimum inspection route has length
(c)(i)
解法一
思路
展开
开放路线从奇数度节点 A 开始，并在另一个奇数度节点结束。若分别考虑以 C、E、J 结束，需要重复的其余奇数节点间最短路径依次为 EJ、CJ、CE；其中 CE 最短，所以应让 J 成为终点。
答题过程
展开
Since the route starts at the odd vertex A, consider the possible repeated paths between the other odd vertices:
The shortest is CE, so C and E should be paired. This leaves A and J as the two odd endpoints. Therefore, Sarita should finish at
(c)(ii)
解法一
思路
展开
闭合路线需增加 357 m，而以 J 结束的开放路线只需重复 CE，增加 168 m。因此两条路线的长度差就是这两个附加长度之差。
答题过程
展开
The open inspection route has length
Hence the difference between the route lengths is