题目
Figure 1 represents a network of roads between 10 cities, A, B, C, D, E, F, G, H, J and K. The number on each edge represents the length, in miles, of the corresponding road.
[The total weight of the network is 253]
One day, Mabintou wishes to travel from A to H. She wishes to minimise the distance she travels.
(a) Use Dijkstra’s algorithm to find the shortest path from A to H. State your path and its length.
On another day, Mabintou wishes to travel from F to K via A.
(b) Find a route of minimum length from F to K via A and state its length.
The roads between the cities need to be inspected. James must travel along each road at least once. He wishes to minimise the length of his inspection route. James will start his inspection route at A and finish at J.
(c) By considering the pairings of all relevant nodes, find the length of James’ route. State the arcs that will need to be traversed twice. You must make your method and working clear.
(d) State the number of times that James will pass through F.
It is now decided to start the inspection route at D. James must minimise the length of his route. He must travel along each road at least once but may finish at any vertex.
(e) State the vertex where the new inspection route will finish.
(f) Calculate the difference between the lengths of the two inspection routes.
题目中文翻译
图 1 表示十个城市 A、B、C、D、E、F、G、H、J 和 K 之间的道路网络。每条边上的数字表示对应道路的长度（单位：英里）。
[网络总权重为 253]
有一天，Mabintou 希望从 A 到 H。她希望最小化旅行距离。
(a) 使用 Dijkstra 算法找到从 A 到 H 的最短路径。写出路径及其长度。
另一天，Mabintou 希望经 A 从 F 到 K。
(b) 找到经 A 从 F 到 K 的最小长度路线并写出其长度。
城市之间的道路需要被检查。James 必须每条道路至少经过一次。他希望最小化检查路线的长度。James 将从 A 开始检查路线，在 J 结束。
(c) 通过考虑所有相关节点的配对，找到 James 路线的长度。写出需要经过两次的弧。必须清楚说明方法和计算过程。
(d) 写出 James 经过 F 的次数。
现在决定从 D 开始检查路线。James 必须最小化路线长度。他必须每条道路至少经过一次，但可以在任何顶点结束。
(e) 写出新检查路线将结束的顶点。
(f) 计算两条检查路线长度之间的差值。