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

[网络总权重为 $205 + 3x$]

Malcolm 希望最小化从家 A 到办公室 H 的驾驶时间。通往 H 的两条道路上的道路工程延误每天不同，因此沿这些道路行驶的时间用 $x$ 表示，其中 $x$ 在任何给定日期是固定的且 $x > 0$。

(a) 使用 Dijkstra 算法找到最小化从 A 到 H 驾驶时间的可能路线。写出每条路线的长度，必要时保留 $x$ 的表达式。

周一，Malcolm 需要检查每条道路。他必须每条道路至少经过一次。他必须从 H 开始并结束，并最小化检查路线所需的总时间。

Malcolm 发现他的最小持续时间检查路线要求他恰好四条道路经过两次，完成检查路线的总时间为 307 分钟。

(b) 计算 Malcolm 周一从 A 到 H 所需的最短时间。必须清楚说明方法和计算过程。

先对不含 $x$ 的部分执行 Dijkstra 算法，严格按产生顺序保留每个工作值。由于进入 $H$ 的三条边分别来自 $D,E,G$，而其中两条权重含 $x$，不能在不知道 $x$ 时确定唯一永久标号；因此分别由 $D,E,G$ 的最终值计算到达 $H$ 的三个候选值，并反向追踪相应路线。

Applying Dijkstra’s algorithm from $A$ gives:

The three possible working values at $H$ are obtained through $D$, $E$ and $G$.

Via $D$:

giving the route

Via $E$:

giving the route

Via $G$:

giving the route

Thus the minimum driving time for a given positive $x$ is the least of

原网络只有 $A,H$ 是奇点。要从 $H$ 出发并回到 $H$ 完成闭合路线，必须把一条 $A$ 到 $H$ 的最短路径重复。题目说明恰好四条道路被重复，因此三条候选路线中只能选择含四条边的 $A-B-D-E-H$；将其长度加到网络总权重并令总和为 307，即可求出周一的 $x$。

The only odd vertices in the original network are $A$ and $H$. Therefore a minimum closed inspection route must repeat a shortest path from $A$ to $H$.

Exactly four roads are traversed twice, so the repeated path is

whose length is $37+2x$.

The total inspection time is therefore

Hence

so

For this value of $x$, the three possible journey times from part (a) are

Therefore the minimum time taken from $A$ to $H$ on Monday is