题目
Figure 5 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F, G and H, represent eight towns. Bronwen needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.
(a) By applying Dijkstra’s algorithm, starting at A, complete the table of least distances in the answer book.
(b) Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Bronwen’s route. Write down the route that gives this upper bound.
A reduced network is formed by deleting A and all arcs that are directly joined to A.
(c) (i) Use Prim’s algorithm, starting at C, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.
(ii) Hence, calculate a lower bound for the length of Bronwen’s route.
(d) Using only the results from (b) and (c), write down the smallest interval that you can be confident contains the length of Bronwen’s optimal route.
题目中文翻译
图 5 模拟了一个道路网络。每条边上的数字表示对应道路的长度（单位：km）。顶点 A、B、C、D、E、F、G 和 H 代表八个城镇。Bronwen 需要访问每个城镇。她将从 A 出发并回到 A，并希望最小化旅行总距离。
(a) 通过应用 Dijkstra 算法，从 A 开始，完成答案本中的最短距离表。
(b) 从 A 开始，使用最近邻算法找到 Bronwen 路线长度的上界。写出给出此上界的路线。
通过删除 A 及其所有直接相连的弧，形成一个简化网络。
(c) (i) 使用 Prim 算法，从 C 开始，为简化网络构建最小生成树。必须清楚说明选择树弧的顺序。
(ii) 由此计算 Bronwen 路线长度的下界。
(d) 仅使用 (b) 和 (c) 的结果，写出你确信包含 Bronwen 最优路线长度的最小区间。