图论中的网络
如何在网络中求最短路径
用它在加权网络上求两点间权重最小的路径。
开始之前
- 会看带权网络：由带数字的边连接的顶点（点）。
- 能准确地把几个数相加。
- 明白一条路线是从起点到终点一串相连的边。
何时使用
用它在加权网络上求两点间权重最小的路径。
步骤
- 为每条边标上权重（距离、时间或成本）。
- 列出起点与终点之间合理的路径。
- 把每条路径的权重相加。
- 比较总和，选最小的。
- 展示每条路径的总和，使比较清晰。
例题
一个网络连接城镇 A、B、C 和 D。道路及其距离为 A–B = 5 km、A–C = 3 km、B–C = 1 km、B–D = 4 km、C–D = 6 km。
求从 A 到 D 的最短路线。
- 给每条边标上权重：A–B = 5 km、A–C = 3 km、B–C = 1 km、B–D = 4 km、C–D = 6 km。
- 列出从 A 到 D 的合理路线：A–B–D、A–C–D、A–C–B–D 和 A–B–C–D。
- 把每条路线上的权重相加：A–B–D = 5 + 4 = 9 km；A–C–D = 3 + 6 = 9 km；A–C–B–D = 3 + 1 + 4 = 8 km；A–B–C–D = 5 + 1 + 6 = 12 km。
- 比较总数 9、9、8 和 12 km，选最小的，即 8 km。
- 列出各总数使比较清楚：路线 A–C–B–D 的 8 km 比其他每条路线都短。
第二个例题（略有变化）
这个网络有五个城镇，权重是以令吉计的车费，因此要相加的路线更多，而经过城镇最少的路线并不是最便宜的。 一个网络连接城镇 P、Q、R、S 和 T。
车费为 P–Q = RM8、P–R = RM5、Q–S = RM4、R–S = RM3、Q–T = RM9、S–T = RM6、R–T = RM15。求从 P 到 T 最便宜的路线。
- 给每条边标上费用：P–Q = RM8、P–R = RM5、Q–S = RM4、R–S = RM3、Q–T = RM9、S–T = RM6、R–T = RM15。
- 列出从 P 到 T 的合理路线：P–Q–T、P–Q–S–T、P–R–T、P–R–S–T 和 P–R–S–Q–T。
- 把每条路线的费用相加：P–Q–T = 8 + 9 = RM17；P–Q–S–T = 8 + 4 + 6 = RM18；P–R–T = 5 + 15 = RM20；P–R–S–T = 5 + 3 + 6 = RM14；P–R–S–Q–T = 5 + 3 + 4 + 9 = RM21。
- 比较总数 RM17、RM18、RM20、RM14 和 RM21，选最小的，即 RM14。
- 列出各总数使比较清楚：P–R–S–T 的 RM14 最便宜，尽管 P–R–T 走的路更少。
公式页面
用 KBAT 题练习
预约试课一小时付费试课 · 当天回复 · 每小时RM50起
常见问题
我必须列出每一条可能的路线吗？
列出从起点到终点每一条合理的路线。明显绕回自己或明显兜远路的可以略去，但任何可能较短的路径都要包括。
漏掉一条路线有风险，因为最短的那条有时正是你没想到要检查的路径。
经过城镇最少的路线一定最短吗？
不一定。边数较少的路线，权重可能较大，总起来反而更长；而经过较多城镇但走的都是又短又便宜的边，总数可能更小。
所以要把每条路线的权重加起来比较总数，而不是只数有几个停靠点。
如果两条路线总数相同该怎么办？
那么两条路线都是最短的，任选一条都算对。好的做法是说明它们相等并写出相同的总数，例如 “A–C–D 和 A–B–D 都是 9 km”。
在演算中列出每个总数，就能清楚说明为什么不止一条路线胜出。