题目
(a) Explain what is meant by the term ‘path’.
Figure 1 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Piatrice wishes to travel from A to J.
(b) Use Dijkstra’s algorithm to find the shortest path Piatrice could take from A to J. State your path and its length.
Piatrice needs to return from J to A via G.
(c) Find the shortest path Piatrice could take from J to A via G and state its length.
题目中文翻译
(a) 解释术语”路径”的含义。
图 1 表示一个道路网络。每条弧上的数字表示对应道路的长度（单位：km）。Piatrice 希望从 A 到 J。
(b) 使用 Dijkstra 算法找到 Piatrice 从 A 到 J 可以走的最短路径。写出路径及其长度。
Piatrice 需要经 G 从 J 返回 A。
(c) 找到 Piatrice 经 G 从 J 到 A 可以走的最短路径并写出其长度。
解答
(a)
解法一
思路
展开
说明路径由首尾相接的边组成，并指出路径不能重复经过顶点。
答题过程
展开
A path is a finite sequence of edges in which the end vertex of each edge is the start vertex of the next edge, with no vertex occurring more than once.
(b)
解法一
思路
展开
从 A 开始使用 Dijkstra 算法。每次固定当前临时标号最小的顶点，并利用与它相邻的边更新其余顶点的临时标号；同时记录产生较小标号的前驱顶点，最后由 J 反向追溯最短路径。
答题过程
展开
Applying Dijkstra’s algorithm from A gives:
| Vertex | Order of labelling | Working values | Final value |
|---|---|---|---|
| A | 1 | 0 | 0 |
| C | 2 | 5 | 5 |
| B | 3 | 8 | 8 |
| F | 4 | 15, 14, 13 | 13 |
| D | 5 | 17, 14 | 14 |
| G | 6 | 24, 23, 20 | 20 |
| E | 7 | 23, 21, (36) | 21 |
| H | 8 | 26 | 26 |
| J | 9 | 40, 35, 33 | 33 |
Tracing back the labels from J gives
Hence the shortest path is
and its length is
(c)
解法一
思路
展开
行程必须经过 G，因此分别取 J 到 G 和 G 到 A 的最短路线，再把两段长度相加。由上一问的永久标号可知，A 到 G 的最短距离为 20。
答题过程
展开
The shortest route from J to G is the direct arc JG, of length 15 km. From G to A, the shortest route is
of length
Therefore the required shortest path is
with length