图 1 表示一个道路网络。每条边上的数字表示对应道路的长度（单位：英里）。Jan 希望从 A 到 J。她希望最小化旅行距离。

[网络总权重为 193]

(a) 使用 Dijkstra 算法找到从 A 到 J 的最短路径。获得最短路径并写出其长度。

周一，Jan 需要从健身房 J 经过办公室 A 回到家 H。

(b) 写出从 J 经过 A 到 H 的最短路径及其长度。

周二，Jan 需要检查每条道路。她必须每条道路至少经过一次。Jan 必须从 A 出发并回到 A。

(c) 使用路线检查算法找到最短检查路线的长度。写出应该重复的道路。必须清楚说明方法和计算过程。

周三，Jan 决定从 G 开始检查路线，但可以在不同的节点结束。检查路线仍然必须每条道路至少经过一次。

(d) 确定路线应该在哪里结束以使检查路线长度最短。必须给出理由并写出路线长度。

从 A 的暂定距离 0 开始，每次永久标记暂定距离最小的顶点，再用它更新所有相邻且未永久标记的顶点。必须按产生顺序保留被更小数值替代的 working values，最后由 J 反向追踪产生其最终值的顶点。

Dijkstra’s algorithm gives the following labels. The working values in each row are listed in the order in which they arise.

For example, the successive working values at $F$ are

The completed labelling diagram is:

Tracing predecessors back from $J$ gives

Therefore, from $A$ to $J$, the shortest path and its length are

由 (a)，J 到 A 的最短路是所得路线的反向，长度为 28。再从 Dijkstra 标号中读取 A 到 H 的最短路 A—B—C—E—H，长度为 20；两段在 A 连接。

The required route is

Its length is

先找出次数为奇数的顶点 A、E、F、G。闭合检查路线需要把四个奇点两两配对，并重复连接每一对的最短路径；必须比较全部三种配对，选择新增长度最小的一种。

The odd vertices are $A$, $E$, $F$ and $G$. The three possible pairings are:

The least added length is 18, so the arcs

should be repeated. Hence the shortest inspection route has length

开放检查路线的起点和终点必须是奇点。指定从 G 出发后，只需在其余奇点 A、E、F 中选一对用最短路径连接；未被配对的奇点就是终点。三种可能中，连接 E 与 F 且不经过 G 的最短路径 E—H—F 长 13，因此终点为 A。

With $G$ fixed as one endpoint, compare shortest paths joining two of the remaining odd vertices $A$, $E$ and $F$ without using $G$.

The least is the path

Repeating $EH$ and $HF$ leaves $G$ and $A$ as the two odd vertices. Therefore the route should finish at

and its minimum length is