题目
Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.
[The total weight of the network is 458]
(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.
The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
(b) By considering the pairings of all relevant nodes, find the length of Claude’s route. State the arcs that will need to be traversed twice.
If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
(c) Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.
题目中文翻译
图 2 表示九个城镇 A、B、C、D、E、F、G、H 和 J 之间的道路网络。每条边上的数字表示对应道路的长度（单位：千米）。
[网络总权重为 458]
(a) (i) 使用 Dijkstra 算法找到从 A 到 J 的最短路径。
(ii) 写出从 A 到 J 的最短路径长度。
城镇之间的道路必须被检查。Claude 必须每条道路至少经过一次。Claude 将从 A 开始检查路线，在 J 结束。Claude 希望最小化检查路线的长度。
(b) 通过考虑所有相关节点的配对，找到 Claude 路线的长度。写出需要经过两次的弧。
如果 Claude 不从 A 开始检查路线并在 J 结束，则可能有更短的检查路线。
(c) 确定 Claude 应该开始和结束的两个城镇，使路线长度最短。给出答案的理由并写出此路线的长度。
解答
(a)
解法一
思路
展开
从 A 赋永久标号 0 开始，每次从已有永久标号的顶点更新相邻顶点的工作值，再把当前最小工作值固定为新的永久标号。记录前驱顶点，最后从 J 逆推即可得到最短路径。
答题过程
展开
Applying Dijkstra’s algorithm from A gives:
| Vertex | Order of labelling | Working values | Final value |
|---|---|---|---|
| A | 1 | 0 | 0 |
| B | 2 | 17 | 17 |
| C | 3 | 28, 25 | 25 |
| D | 4 | 39, 37, 35 | 35 |
| E | 5 | 45 | 45 |
| F | 6 | 55, 50, 47 | 47 |
| G | 7 | 72, 67 | 67 |
| H | 8 | 92, 78 | 78 |
| J | 9 | 90, 87, 85, 83 | 83 |
Tracing back the updates that produced the final values gives
Therefore:
(i) The shortest path is
(ii) Its length is
(b)
解法一
思路
展开
原网络的奇度顶点是 A、B、F、H，而开放路线指定从 A 到 J，因此最终奇度顶点应为 A、J。把两组奇点作对称差后，需要配对的是 B、F、H、J。列出三种完整配对，选择总距离最小的一组，并把最短路径还原成实际重复的弧。
答题过程
展开
The vertices that must be paired are B, F, H and J. The three possible pairings are
The minimum pairing is .
The shortest path from B to F is , so the arcs that must be traversed twice are
Hence Claude’s minimum route length is
(c)
解法一
思路
展开
若起点和终点可以自由选择，最好让其中两个原有奇度顶点直接作为路线端点，余下两个奇度顶点只需按最短距离配对。四个奇度顶点 A、B、F、H 中，最短的一对是 A、B，因此应把另外两点 F、H 选为起点和终点。
答题过程
展开
The odd vertices are A, B, F and H. The shortest path between any pair of these vertices is , of length 17 km.
Therefore A and B should be paired, leaving F and H as the two odd endpoints. Claude should start at F and finish at H, or vice versa.
The minimum route length is
Thus the required endpoints are