题目
Figure 3 represents a network of roads between nine parks, A, B, C, D, E, F, G, H and J. The number on each edge represents the length, in miles, of the corresponding road.
[The total weight of the network is 315]
(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 parks need to be inspected. Robin must travel along each road at least once. Robin wishes to minimise the length of the inspection route. Robin will start the inspection route at C and finish at E.
(b) By considering the pairings of all relevant nodes, find the length of Robin’s route.
(c) State the number of times Robin will pass through G.
It is now decided to start and finish the inspection route at A. Robin must still minimise the length of the route and travel along each road at least once.
(d) Calculate the difference between the lengths of the two inspection routes.
(e) State the edges that need to be traversed twice in the route that starts and finishes at A, but do not need to be traversed twice in the route that starts at C and finishes at E.
题目中文翻译
图 3 表示九个公园 A、B、C、D、E、F、G、H 和 J 之间的道路网络。每条边上的数字表示对应道路的长度（单位：英里）。
[网络总权重为 315]
(a) (i) 使用 Dijkstra 算法找到从 A 到 J 的最短路径。
(ii) 写出从 A 到 J 的最短路径长度。
公园之间的道路需要被检查。Robin 必须每条道路至少经过一次。Robin 希望最小化检查路线的长度。Robin 将从 C 开始检查路线，在 E 结束。
(b) 通过考虑所有相关节点的配对，找到 Robin 路线的长度。
(c) 写出 Robin 经过 G 的次数。
现在决定从 A 开始并结束检查路线。Robin 仍然必须最小化路线长度并每条道路至少经过一次。
(d) 计算两条检查路线长度之间的差值。
(e) 写出在从 A 开始并结束的路线中需要经过两次，但在从 C 开始到 E 结束的路线中不需要经过两次的边。