题目
Figure 4 represents a network of roads. The number on each arc represents the length, in miles, of the corresponding road. Tamasi, who lives at A, needs to collect a caravan. Tamasi can collect a caravan from either J or K.
Tamasi decides to use Dijkstra’s algorithm once to find the shortest routes between A and J and between A and K.
(a) State, with a reason, which vertex should be chosen as the starting vertex for the algorithm.
(b) Use Dijkstra’s algorithm to find the shortest routes from A to J and from A to K. You should state the routes and their corresponding lengths.
Tamasi’s brother lives at F. He needs to visit Tamasi at A and then visit their mother who lives at H.
(c) Find a route of minimal length that goes from F to H via A.
题目中文翻译
图 4 表示一个道路网络。每条弧上的数字表示对应道路的长度（单位：英里）。住在 A 的 Tamasi 需要取一辆旅居车。Tamasi 可以从 J 或 K 取旅居车。
Tamasi 决定使用 Dijkstra 算法一次来找到 A 和 J 之间以及 A 和 K 之间的最短路线。
(a) 说明应选择哪个顶点作为算法的起始顶点，并给出理由。
(b) 使用 Dijkstra 算法找到从 A 到 J 和从 A 到 K 的最短路线。应写出路线及其对应的长度。
Tamasi 的兄弟住在 F。他需要去 A 拜访 Tamasi，然后去 H 拜访他们的母亲。
(c) 找到从 F 经 A 到 H 的最小长度路线。
解答
(a)
解法一
思路
展开
题目要求只运行一次 Dijkstra 算法，却同时求 A 到 J 和 A 到 K 的最短路线。因此应从两条目标路线共同包含的端点 A 开始，这一次运行便能得到 A 到所有其他顶点的最短距离。
答题过程
展开
The starting vertex should be
Both required routes contain A, and one application of Dijkstra’s algorithm from A finds the shortest distance from A to every other vertex, including J and K.
(b)
解法一
思路
展开
从 A 的永久标号 0 开始，不断更新相邻顶点的工作值，并按当前最小值依次固定顶点。记录每个最终值来自哪一个前驱顶点，便可分别从 J、K 逆推回 A。
答题过程
展开
Applying Dijkstra’s algorithm from A gives:
| Vertex | Order of labelling | Working values | Final value |
|---|---|---|---|
| A | 1 | 0 | 0 |
| C | 2 | 12 | 12 |
| D | 3 | 24, 23 | 23 |
| B | 4 | 32, 31 | 31 |
| G | 5 | 43, 40 | 40 |
| E | 6 | 43, 41 | 41 |
| F | 7 | 51, 49, 48 | 48 |
| H | 8 | 55, 51 | 51 |
| J | 9 | 84, 82, 80 | 80 |
| K | 10 | 92, 89, 81 | 81 |
Tracing back from J gives
with length
Tracing back from K gives
with length
Therefore the required shortest routes are
and
(c)
解法一
思路
展开
“经 A”把路线分成 F 到 A 与 A 到 H 两段。两段都必须各自取最短路径，否则可替换其中一段而缩短总路线。利用上一问的 Dijkstra 标号，反向读取 A 到 F 的最短路，再接上 A 到 H 的最短路。
答题过程
展开
The shortest route from F to A is the reverse of the shortest route from A to F:
with length 48 miles.
The shortest route from A to H is
with length 51 miles.
Hence a route of minimum length from F to H via A is
Its total length is