题目
Figure 2 represents a network of roads between nine towns, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in kilometres, of the corresponding road.
[The total weight of the network is 458]
(a) (i) Use Dijkstra’s algorithm to find the shortest path from A to J.
(ii) State the length of the shortest path from A to J.
The roads between the towns must be inspected. Claude must travel along each road at least once. Claude will start the inspection route at A and finish at J. Claude wishes to minimise the length of the inspection route.
(b) By considering the pairings of all relevant nodes, find the length of Claude’s route. State the arcs that will need to be traversed twice.
If Claude does not start the inspection route at A and finish at J, a shorter inspection route is possible.
(c) Determine the two towns at which Claude should start and finish so that the route has minimum length. Give a reason for your answer and state the length of this route.
题目中文翻译
图 2 表示九个城镇 A、B、C、D、E、F、G、H 和 J 之间的道路网络。每条边上的数字表示对应道路的长度（单位：千米）。
[网络总权重为 458]
(a) (i) 使用 Dijkstra 算法找到从 A 到 J 的最短路径。
(ii) 写出从 A 到 J 的最短路径长度。
城镇之间的道路必须被检查。Claude 必须每条道路至少经过一次。Claude 将从 A 开始检查路线，在 J 结束。Claude 希望最小化检查路线的长度。
(b) 通过考虑所有相关节点的配对，找到 Claude 路线的长度。写出需要经过两次的弧。
如果 Claude 不从 A 开始检查路线并在 J 结束，则可能有更短的检查路线。
(c) 确定 Claude 应该开始和结束的两个城镇，使路线长度最短。给出答案的理由并写出此路线的长度。