第21讲最短路线.docVIP

第21讲 最短路线 在日常生活中、工作中，经常会遇到有关行程路线的问题。比如：邮递员送信，要穿遍所有的街道，为了少走冤枉路，需要选择一条最短的路线；旅行者希望寻求最佳旅行路线，以求能够最近和路而达到目的地，等等。这样的问题，就是所谓“最短路线问题”。 例题与方法 假如直线AB是一条公路，公路两侧有甲、乙两个村子（图1）。现在要在公路上修建一个公共汽车站，让这两个村子的人到汽车站的路线之和最短。问“车站应该建在什么地方？ 一个邮递员投送信件的街道如图3所示，图上数字表示各段街道的千米数。他从邮局出发，要走遍各街道，最后回到邮局。问下次什么样的路线最合理？全程要走多少千米？ 图5中的线段表示的是小明从家到学校所能经过的所有街道。小明上学走路的方向都是向东或向南，因为他不想偏离学校的方向而走冤枉路。那么小明从家到学校可以有我少条不同的路线？ 如图8，从甲地到乙地最近的道路有几条？ 某城市的街道非常整齐，如图10所示。从本南角A处到东北角B处要求走最近的路，并且不能通过十字路口C（正在修路），共有多少种不同的走法？ C B→ →A 练习与思考 图13是一个街区街道的平面图。邮递员从邮局出发，跑遍所有街道投送信件。请你为他安排一条最短的路线，并按图中标出的千米数算出这条路线的长度（单位：千米）。 图14是一个街道平面图。王宏要从A处到B处，在不走回头路，不走重复路的条件下，可以有多少种不同的路线？请你用交叉点上标数的方法计算一下。 从学校到少年宫有4条东西向的马路和3条南北向的马路相通。如图15，李楠从学校出发，步行到少年宫（只放向东或向南行进），最多有多少种不同的行走路线？ 如图16，从P到Q共有多少咱不同的最短路线？ 如图17所示，某城市的街道图，若从AZ走到B（只能由北向南、由西向东），则共有多少种不同的走法？ 如图18所示，从甲地到乙地，最近的道路有几条？ 图19为某城市的街道示意图，C处正在挖下水道，不能通车，众A到B处的最短路线共有多少条？ 如图20所示是一个街道的平面图，在不走回头路、不走重复路和条件下，可以有多少种不同的走法？ 我们一直在努力！ 1 2 4 2 1 3 小明家 ↑北 △ □ 学校 甲 乙 2 1 2 2 △ 邮局 2 1 1 3 A B 学校 A B 北 C M ↑ D N E 少年宫 -F G H P Q A B 乙 甲 B A C A B 1