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

[网络总权重为 253]

有一天，Mabintou 希望从 A 到 H。她希望最小化旅行距离。

(a) 使用 Dijkstra 算法找到从 A 到 H 的最短路径。写出路径及其长度。

另一天，Mabintou 希望经 A 从 F 到 K。

(b) 找到经 A 从 F 到 K 的最小长度路线并写出其长度。

城市之间的道路需要被检查。James 必须每条道路至少经过一次。他希望最小化检查路线的长度。James 将从 A 开始检查路线，在 J 结束。

(c) 通过考虑所有相关节点的配对，找到 James 路线的长度。写出需要经过两次的弧。必须清楚说明方法和计算过程。

(d) 写出 James 经过 F 的次数。

现在决定从 D 开始检查路线。James 必须最小化路线长度。他必须每条道路至少经过一次，但可以在任何顶点结束。

(e) 写出新检查路线将结束的顶点。

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

从 $A$ 赋永久标号 0 开始，每次选择当前工作值最小的顶点成为下一个永久标号，并按该顶点更新所有相邻顶点。工作值必须按产生顺序保留；到 $H$ 获得永久标号后，再沿产生最终值的前驱顶点反向追踪最短路径。

Applying Dijkstra’s algorithm from $A$ gives:

Tracing back the final labels gives

Therefore the shortest path is

with length

“经 $A$”把路线分成 $F$ 到 $A$ 与 $A$ 到 $K$ 两段，两段分别取最短路线后相加。由于道路无方向，(a) 的标号也能帮助读取这些最短距离。

A shortest route from $F$ to $A$ is

with length

A shortest route from $A$ to $K$ is

with length

Hence a minimum route from $F$ to $K$ via $A$ is

and its length is

原网络的奇点是 $C,E$。路线指定从 $A$ 开始、在 $J$ 结束，因此最终只有 $A,J$ 应为奇点；把这两个端点与原奇点合并考虑，需要为 $A,C,E,J$ 选择总距离最小的配对。四个顶点共有三种不同配对，必须全部比较。

The relevant vertices are $A,C,E$ and $J$. The three possible pairings are:

The minimum pairing is therefore $AC+EJ$.

The shortest route from $A$ to $C$ is $A-B-C$, and the shortest route from $E$ to $J$ is $E-F-K-J$. Hence the arcs to be traversed twice are

The minimum inspection-route length is

在增广后的网络中，$F$ 原本连接六条边，而 (c) 又把 $EF$ 与 $FK$ 各重复一次，所以增广后 $F$ 的度数是 8。路线并非从 $F$ 开始或结束，因此每次经过 $F$ 会使用一条进入边和一条离开边。

The augmented degree of $F$ is

Therefore the number of times James passes through $F$ is

新路线从偶点 $D$ 开始，而原网络的奇点为 $C,E$。若在奇点 $C$ 结束，只需重复连接 $D,E$ 的最短路线；该路线就是权重为 10 的边 $DE$，新增长度最小。

To start at $D$ and finish at $C$, only the shortest path between $D$ and $E$ needs to be repeated. This is the single edge $DE$, of length $10$ miles.

Hence the new inspection route should finish at

第一条检查路线的长度由 (c) 得到。第二条路线只需在网络总权重 253 上加上重复边 $DE$ 的长度 10，再计算两者之差。

The new route has length

Therefore the difference between the two route lengths is