KBAT 题

KBAT 题：寻找最短路径

要列出来。评卷者为比较给分，所以逐条写出路径及其合计，一旦某处算错还能保住分。在小网络里最短的未必是看起来最直的，正如封路变式所示。列出既保分也更准。

顶点是一个位置，这里是城镇，画成一个点。边是两个顶点之间的连接，这里是道路，画成一条线并标注长度或权重。用对这些术语很重要，因为考题及其评分正是用这些词写的。

不。权重可以是距离、时间、成本或容量，视情境而定。累加前务必读清数字代表什么，因为最短距离路径与最便宜路径可能不同。答错量是常见的 KBAT 失误，先确定权重的含义。

一道使用加权网络的 KBAT 式题目，测试你能否建模而非仅计算。

由 spmmath.com.my 编辑团队撰写。

为情境建模

一次配送要经过几个城镇，城镇间距离已知。把它画成加权网络，城镇为顶点、道路为加权边。

列出可能的路径、把每条的权重相加、选最小的。完整答案要展示每条路径的合计。

快递员须从城镇 P 前往城镇 T。道路及其长度（km）为 P–Q = 8、P–R = 5、R–Q = 2、Q–T = 6、R–S = 7、S–T = 3。

求 P 到 T 的最短路径。真正要问的是：把道路建成加权网络，再比较完整路径，而非只挑一条最短的路。

画出网络：城镇 P、Q、R、S、T 为顶点；每条道路为标注长度的边。
列出 P 到 T 的每条路径。路径 1：P–Q–T。路径 2：P–R–Q–T。路径 3：P–R–S–T。路径 4：P–Q–R–S–T。
累加权重：路径 1 = 8 + 6 = 14 km。路径 2 = 5 + 2 + 6 = 13 km。路径 3 = 5 + 7 + 3 = 15 km。路径 4 = 8 + 2 + 7 + 3 = 20 km。
最小合计是 13 km，所以最短路径是 P–R–Q–T，共 13 km。

扫过四个合计 14、13、15 和 20 来检验 13 km 确实最小，没有路径优于 13。考官可加的变式：R–Q 路段维修封闭。

去掉它后只剩 P–Q–T = 14 km 和 P–R–S–T = 15 km，最短变为 P–Q–T 的 14 km。去掉一条边就能改变整个答案，所以要列路径而非相信第一条看似短的路。

预约试课一小时付费试课 · 当天回复 · 每小时RM50起

我必须列出每条路径，还是直接看出最短的就行？

要列出来。评卷者为比较给分，所以逐条写出路径及其合计，一旦某处算错还能保住分。

在小网络里最短的未必是看起来最直的，正如封路变式所示。列出既保分也更准。

这里顶点和边有什么区别？

顶点是一个位置，这里是城镇，画成一个点。边是两个顶点之间的连接，这里是道路，画成一条线并标注长度或权重。

用对这些术语很重要，因为考题及其评分正是用这些词写的。

权重一定是距离吗？

不。权重可以是距离、时间、成本或容量，视情境而定。

累加前务必读清数字代表什么，因为最短距离路径与最便宜路径可能不同。答错量是常见的 KBAT 失误，先确定权重的含义。