图 4 模拟了一个道路网络。每条边上的数字表示沿对应道路行驶所需的时间（单位：分钟）。顶点 A、B、C、D、E、F、G、H 和 J 代表九个城镇。Ezra 希望尽快从 A 到 H。城镇 G 和 J 之间的行驶时间未知，用 $x$ 分钟表示。

[网络总权重为 $383 + x$]

将使用 Dijkstra 算法找到从 A 到 H 的最快时间。答案本中图 1 上 A 和 J 处的”标注顺序”和”最终值”以及 J 处的”工作值”已完成。

(a) 使用 Dijkstra 算法找到从 A 到 H 的最快时间。写出最快路线。

Ezra 需要沿每条道路行驶以检查其是否状况良好。他希望最小化遍历网络所需的总时间。Ezra 计划从 A 开始并结束检查路线。已知他的路线至少需要 440 分钟。

(b) 使用路线检查算法和完成的图 1 找到 $x$ 的可能取值范围。

(c) 写出 Ezra 的一条可能路线。

一条从 D 到 H 的新直接道路正在建设中，行驶需要 25 分钟。Ezra 将在这条新道路中包含在从 A 开始并结束的最小长度检查路线中。已知此检查路线恰好需要 488 分钟。

(d) 确定 $x$ 的值。必须给出理由。

从 A 的暂定距离 0 开始，每次永久标记当前暂定距离最小的顶点，并按永久标记顺序更新相邻顶点。被更小数值替代的 working values 仍按产生顺序保留；最后从 H 反向追踪产生最终值的顶点。

Dijkstra’s algorithm gives:

For example, the working values at $H$ arise in the order

The completed labelling diagram is:

Tracing back from $H$ gives the route

Its time is

网络的奇点为 A、D、E、H。闭合检查路线必须把它们两两配对并重复相应最短路径，因此要比较全部三种配对。最小新增量给出检查路线长度；再结合“至少 440 分钟”和 J 已填的 working values，可分别得到 $x$ 的下界与上界。

The odd vertices are $A$, $D$, $E$ and $H$. The possible pairings are:

The minimum added time is 33 minutes. Hence the minimum inspection time is

Since the inspection route takes at least 440 minutes,

so

At $J$, the working value $91$ is replaced by $61+x$. Therefore

which gives $x<30$. Combining the two restrictions,

采用 (b) 的最优配对，需要把 AD 和 EH 各重复一次。写出一条从 A 出发回到 A 的闭合路线，并逐项检查每条原有道路至少出现一次、重复边恰为 AD 和 EH。

One possible inspection route is

This route starts and finishes at $A$, traverses every edge, and repeats $AD$ and $EH$.

原网络的奇点是 A、D、E、H。加入新边 DH 后，D 与 H 的次数各增加 1，因而变为偶点，只剩 A、E 为奇点。要得到闭合检查路线，必须重复 A 到 E 的最短路径，其长度由 (a) 的标号可得为 52。

After adding the new edge $DH$, the only odd vertices are $A$ and $E$. The shortest path from $A$ to $E$ has length 52, so the minimum inspection time is

It is given that this equals 488, hence

and therefore

This also satisfies the range $24\leqslant x<30$ found in (b).