图 3 表示九个公园 A、B、C、D、E、F、G、H 和 J 之间的道路网络。每条边上的数字表示对应道路的长度（单位：英里）。

[网络总权重为 315]

(a) (i) 使用 Dijkstra 算法找到从 A 到 J 的最短路径。

(ii) 写出从 A 到 J 的最短路径长度。

公园之间的道路需要被检查。Robin 必须每条道路至少经过一次。Robin 希望最小化检查路线的长度。Robin 将从 C 开始检查路线，在 E 结束。

(b) 通过考虑所有相关节点的配对，找到 Robin 路线的长度。

(c) 写出 Robin 经过 G 的次数。

现在决定从 A 开始并结束检查路线。Robin 仍然必须最小化路线长度并每条道路至少经过一次。

(d) 计算两条检查路线长度之间的差值。

(e) 写出在从 A 开始并结束的路线中需要经过两次，但在从 C 开始到 E 结束的路线中不需要经过两次的边。

从 A 开始执行 Dijkstra 算法。每次永久标记当前最小的暂定值，并按节点永久标记的先后顺序记录工作值。最后从 J 反向追溯产生最小值的前驱节点，即可得到最短路径。

Applying Dijkstra’s algorithm from A gives:

The completed labelling diagram is:

Tracing predecessors back from J gives

Hence the shortest path from A to J is

J 的最终标号就是从 A 到 J 的最短距离；也可以把 (a)(i) 所得路径上的边长相加核对。

The length of the shortest path is

原网络的奇度节点为 A、J。开放巡检路线指定从 C 出发、到 E 结束，因此增补边后奇度节点必须改为 C、E。于是要对 A、C、E、J 作三种不同配对，比较每组最短路径总长，并选最小者加到网络总权重 315 上。

The three possible pairings of A, C, E and J are:

The minimum additional length is therefore $52$ miles. Hence Robin’s shortest route has length

最优增补路线重复 E—H—G—J，所以与 G 相连的 GH、GJ 各多走一次。G 原本度数为 4，增补后度数为 6；G 不是起点或终点，因此巡检路线每次进入后都要离开，经过次数为 $6\div2$。

In the optimal route, edges GH and GJ are each repeated. Thus the degree of G in the augmented network is

Therefore Robin passes through G

若改为从 A 出发并回到 A，就必须把原网络的两个奇度节点 A、J 配成一对，因此要重复它们之间长 67 的最短路径。两种路线都包含原网络总权重 315，所以只需比较各自增加的 67 与 52。

For a closed route, the shortest A—J path of length $67$ miles must be repeated. The difference between the two inspection-route lengths is therefore

闭合路线重复的 A—J 最短路径为 A—D—C—F—E—H—G—J；开放路线已经重复 A—D—C 与 E—H—G—J。比较两者，只有中间的 CF、FE 是闭合路线额外需要重复的边。

The closed route repeats

whereas the route from C to E repeats A—D—C and E—H—G—J. Therefore the required edges are