题目
Figure 2 models a network of tracks between nine ranger stations, A, B, C, D, E, F, G, H and J, in a forest. The number on each edge gives the time, in minutes, to travel along the corresponding track. The forest ranger wishes to travel from A to J as quickly as possible.
(a) Use Dijkstra’s algorithm to find the shortest time needed to travel from A to J.
State the quickest route.
(b) Hence determine the weight of the minimum spanning tree for the network given in Figure 2. Give a reason for your answer.
You do not need to find the minimum spanning tree.
题目中文翻译
图 2 表示森林中九个护林站 A、B、C、D、E、F、G、H 和 J 之间的小径网络。每条边上的数字表示沿相应小径行进所需的时间（单位：分钟）。护林员希望尽快从 A 前往 J。
(a) 使用 Dijkstra 算法求从 A 前往 J 所需的最短时间。
写出最快路线。
(b) 由此确定图 2 所示网络的最小生成树权重，并说明理由。
无需求出最小生成树。
解答
(a)
解法一
思路
展开
从 A 开始运行 Dijkstra 算法。每次固定当前临时标号最小的顶点，并按顶点被永久标号的次序更新相邻顶点；工作值的先后次序也要保留。最后从 J 沿产生最小标号的前驱顶点反向追溯。
答题过程
展开
Applying Dijkstra’s algorithm from A gives:
| Vertex | Order of labelling | Working values | Final value |
|---|---|---|---|
| A | 1 | 0 | 0 |
| C | 2 | 10 | 10 |
| B | 3 | 27, 18 | 18 |
| F | 4 | 48, 27 | 27 |
| G | 5 | 32 | 32 |
| D | 6 | 52, 50, 47, 45 | 45 |
| E | 7 | 71, 61, 52 | 52 |
| H | 8 | 83, 63, 61 | 61 |
| J | 9 | 91, 75, 74 | 74 |
Tracing back from J gives
Hence the quickest route is
and the shortest time is
(b)
解法一
思路
展开
承接上一问：所得最快路线没有重复顶点，并且恰好经过网络中的全部九个顶点，因此这条路径本身连接全部顶点。按照官方评分资料的结论，它的权重就是该网络最小生成树的权重。
答题过程
展开
The quickest route found in part (a) passes through all nine vertices of the network. It therefore gives the minimum spanning tree for this network.
Hence the weight of the minimum spanning tree is