《最短线路问题.docx》由会员分享，可在线阅读，更多相关《最短线路问题.docx（2页珍藏版）》请在三一文库上搜索。
1、最短线路问题知识点总结：1、两点之间，线段最短：连接两点之间的线段， 为两点之间的最短路线； A、B 两点在直线 CD的同侧，做 A 点关于直线 CD的对称点 A，连接 A与 B 的线段与直线 CD交于 E 点，则AE+BE最短；2、标数法：适用于求从点 A 到点 B 的最短路线的条数；从起点到达任何一点的最短路线数，都等于从起点出发到达与这一点相邻的点的最短路线数之和。 本质上是利用加法原理进行分类计数。例 右图是一张道路示意图， 每段路上的数字表示小明走这段路所需要的时间 （单位：分）。小明从 A 到 B 最快要几分钟？分析与解： 我们采用分析排除法，将道路图逐步简化。从 A 到 O有两条
2、路， A C O用 6 分钟， AFO用 7 分钟，排除后者，可将 FO抹去，但 AF 不能抹去，因为从 A 到 B 还有其它路线经过 AF，简化为左下图。从 A 到 E 还剩两条路， ACGE 用 12 分钟， ACOE 用 10 分钟，排除前者，可将 CG，GE抹去，简化为右上图。从 A 到 D 还剩两条路， A C O D 用 12 分钟，A H D 用 13 分钟，排除后者，可将 AH，HD抹去，简化为左下图。从 A 到 B 还剩两条路， ACOEB 用 17 分钟， ACODB 用 16 分钟，排除前者，可将 OE，EB抹去，简化为右上图。小明按 ACODB 走最快，用 16 分钟。