题目
Figure 1 represents a network of roads between nine villages, A, B, C, D, E, F, G, H and J. The number on each arc is the time taken, in minutes, to drive along the corresponding road.
(a) (i) Use Dijkstra’s algorithm to determine the fastest route from A to H.
(ii) State the fastest time.
The roads EF and GJ are now closed for maintenance.
(b) Calculate how much more time Liliya’s drive will now take.
题目中文翻译
图 1 表示九个村庄 A、B、C、D、E、F、G、H 和 J 之间的道路网络。每条弧上的数字是沿对应道路行驶所需的时间（单位：分钟）。
(a) (i) 使用 Dijkstra 算法确定从 A 到 H 的最快路线。
(ii) 说明最快时间。
道路 EF 和 GJ 现因维护而关闭。
(b) 计算 Liliya 的行驶时间现在会增加多少。
解答
(a)(i)
解法一
思路
展开
从 A 赋永久值 0 开始，每次选取当前最小的临时值作为下一个永久标号，再用该点更新所有相邻点。工作值必须按产生顺序保留；最后从 H 沿着产生永久值的前驱反向追踪，即可得到最快路线。
答题过程
展开
Applying Dijkstra’s algorithm from A gives
| Vertex | Order of labelling | Working values | Final value |
|---|---|---|---|
| A | 1 | - | 0 |
| C | 2 | 9 | 9 |
| B | 3 | 18, 17 | 17 |
| D | 4 | 23, 21 | 21 |
| E | 5 | 27, 26 | 26 |
| F | 6 | 37, 35, 33 | 33 |
| G | 7 | 43, 42 | 42 |
| J | 8 | 50, 48 | 48 |
| H | 9 | 58, 55, 53 | 53 |
Backtracking from H through the vertices that produced the final labels gives
(a)(ii)
解法一
思路
展开
H 的永久值就是从 A 到 H 的最短距离；由于弧权表示分钟，所以直接读取 H 的最终标号 53。
答题过程
展开
The final label at H is 53, so the fastest time is
(b)
解法一
思路
展开
删除 EF 与 GJ 后重新寻找最短路线。从 A 到 F 的新最短路径是 A-C-D-F，需 35 分钟；从 F 到 H 可走直接道路 FH，需 22 分钟。因此新最快时间为 57 分钟，再减去原来的 53 分钟。
答题过程
展开
With EF and GJ closed, a new fastest route is A-C-D-F-H. Its time is
Therefore, the increase is
解法二
思路
展开
也可以只比较受封路影响的两段。原路线从 A 到 F 经 A-C-B-E-F，新路线改经 A-C-D-F，多 2 分钟；原路线从 F 到 H 经 F-G-J-H，新路线可经 F-J-H，也多 2 分钟。
答题过程
展开
For the first affected section,
so this section takes 2 minutes longer.
For the second affected section,
so this section also takes 2 minutes longer. Hence the total increase is