题目

Problem

Figure 4 models a network of roads. The number on each edge gives the time, in minutes, to travel along the corresponding road. The vertices, A, B, C, D, E, F, G, H and J represent nine towns. Ezra wishes to travel from A to H as fast as possible. The time taken to travel between towns G and J is unknown and is denoted by $x$ minutes.

[The total weight of the network is $383 + x$ ]

Dijkstra’s algorithm is to be used to find the fastest time to travel from A to H. On Diagram 1 in the answer book the “Order of labelling” and “Final value” at A and J, and the “Working values” at J, have already been completed.

(a) Use Dijkstra’s algorithm to find the fastest time to travel from A to H. State the quickest route.

(6)

Ezra needs to travel along each road to check it is in good repair. He wishes to minimise the total time required to traverse the network. Ezra plans to start and finish his inspection route at A. It is given that his route will take at least 440 minutes.

(b) Use the route inspection algorithm and the completed Diagram 1 to find the range of possible values of $x$ .

(6)

(1)

A new direct road from D to H is under construction and will take 25 minutes to travel along. Ezra will include this new road in a minimum length inspection route starting and finishing at A. It is given that this inspection route takes exactly 488 minutes.

(d) Determine the value of $x$ . You must give reasons for your answer.

(2)

题目中文翻译

图 4 模拟了一个道路网络。每条边上的数字表示沿对应道路行驶所需的时间（单位：分钟）。顶点 A、B、C、D、E、F、G、H 和 J 代表九个城镇。Ezra 希望尽快从 A 到 H。城镇 G 和 J 之间的行驶时间未知，用 $x$ 分钟表示。

[网络总权重为 $383 + x$ ]

将使用 Dijkstra 算法找到从 A 到 H 的最快时间。答案本中图 1 上 A 和 J 处的”标注顺序”和”最终值”以及 J 处的”工作值”已完成。

(a) 使用 Dijkstra 算法找到从 A 到 H 的最快时间。写出最快路线。

Ezra 需要沿每条道路行驶以检查其是否状况良好。他希望最小化遍历网络所需的总时间。Ezra 计划从 A 开始并结束检查路线。已知他的路线至少需要 440 分钟。

(b) 使用路线检查算法和完成的图 1 找到 $x$ 的可能取值范围。

一条从 D 到 H 的新直接道路正在建设中，行驶需要 25 分钟。Ezra 将在这条新道路中包含在从 A 开始并结束的最小长度检查路线中。已知此检查路线恰好需要 488 分钟。

(d) 确定 $x$ 的值。必须给出理由。

IAL 2022 June D1 Q6

题目

解答