题目
Figure 3 models a network of roads. The number on each edge gives the time taken, in minutes, to travel along the corresponding road.
(a) Use Dijkstra’s algorithm to find the shortest time needed to travel from A to J. State the quickest route.
Alan needs to travel along all the roads to check that they are in good repair. He wishes to complete his route as quickly as possible and will start at his home, H, and finish at his workplace, D.
(b) By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in Alan’s inspection route from H to D. You must make your method and working clear.
For Alan’s inspection route from H to D
(c) (i) state the number of times vertex C will appear,
(ii) state the number of times vertex D will appear.
(d) Determine whether it would be quicker for Alan to start and finish his inspection route at H, instead of starting at H and finishing at D. You must explain your reasoning and show all your working.
(Total 15 marks)
题目中文翻译
图 3 表示一个道路网络。每条边上的数字表示沿对应道路行驶所需的时间，单位是分钟。
(a) 使用 Dijkstra 算法求从 A 到 J 所需的最短时间，并写出最快路线。
Alan 需要沿所有道路行驶，以检查道路是否状况良好。他希望尽快完成路线，并且会从他的家 H 出发，在他的工作地点 D 结束。
(b) 通过考虑所有相关节点的配对，找出 Alan 从 H 到 D 的巡检路线中需要重复经过的边。你必须清楚展示你的方法和计算过程。
对于 Alan 从 H 到 D 的巡检路线：
(c) (i) 写出顶点 C 将出现的次数；
(ii) 写出顶点 D 将出现的次数。
(d) 判断如果 Alan 从 H 出发并最终回到 H，而不是从 H 出发并在 D 结束，是否会更快。你必须解释你的理由并展示所有计算过程。