图 3 表示一个道路网络。每条边上的数字表示沿对应道路行驶所需的时间，单位是分钟。

(a) 使用 Dijkstra 算法求从 A 到 J 所需的最短时间，并写出最快路线。

Alan 需要沿所有道路行驶，以检查道路是否状况良好。他希望尽快完成路线，并且会从他的家 H 出发，在他的工作地点 D 结束。

(b) 通过考虑所有相关节点的配对，找出 Alan 从 H 到 D 的巡检路线中需要重复经过的边。你必须清楚展示你的方法和计算过程。

对于 Alan 从 H 到 D 的巡检路线：

(c) (i) 写出顶点 C 将出现的次数；

(ii) 写出顶点 D 将出现的次数。

(d) 判断如果 Alan 从 H 出发并最终回到 H，而不是从 H 出发并在 D 结束，是否会更快。你必须解释你的理由并展示所有计算过程。

从 A 赋永久标号 0，每次把当前最小的暂定标号固定，并用新固定节点更新相邻节点。依次固定 C、E、B、D、F、H、G、J；再从 J 沿产生最终标号的前驱反向追踪，即可得到最短路线。

Applying Dijkstra’s algorithm gives:

Therefore the shortest time is

along the route

原网络的奇点为 A、J。开放路线指定从 H 到 D，因此把原奇点与两个端点作对称差后，需要配对的节点是 A、D、H、J。列出三种不同配对并比较其最短路总权，选出总权最小的一组。

The relevant vertices are $A,D,H$ and $J$. The three possible pairings are

For the minimum pairing, the shortest path from $A$ to $D$ is $A-C-B-D$, while $H$ and $J$ are joined directly. Hence the arcs that must be traversed twice are

加入重复边 AC、BC 后，C 的度数由 6 增至 8。C 不是路线端点，因此在欧拉迹中每次到达都要沿另一条边离开，出现次数为度数的一半。

After the repeated arcs are added,

Since $C$ is not an endpoint of the route, it appears

D 原有度数 4，重复 BD 后度数变为 5。由于 D 是开放路线的终点，最后一次到达后不再离开，所以出现次数比“成对使用边”的次数多一次，即为 3。

After $BD$ is repeated,

As $D$ is the finishing vertex, it appears

若改为从 H 出发并回到 H，原图仅需把奇点 A、J 之间的最短路径重复一次，额外路程为 45。原来的 H 到 D 开放路线只需增加权值 40；比较两者的总时间即可。

For a closed route from $H$ to $H$, the only odd vertices $A$ and $J$ must be paired, adding the shortest-path weight

Thus the closed route takes

The open route from $H$ to $D$ takes

Since $314>309$, it is quicker to start at $H$ and finish at $D$.