精品初中数学竞赛专题讲解最短路径问题(最全资料)之欧阳音创编_图文.pdfVIP

欧阳音创编2021.03.11欧阳音创编

2021.03.11

初中数学竞赛专题讲解最

短路径问题

时间：2021.03.11创作：欧阳音

【问题概述】最短路径问题是图论研究中的一个经

典算法问题，旨在寻找图（由结点和路径组成

的）中两结点之间的最短路径．算法具体的形式包

括：

①确定起点的最短路径问题-即已知起始结点，

求最短路径的问题．

②确定终点的最短路径问题-与确定起点的问题

相反，该问题是已知终结结点，求最短路径的问

题．

③确定起点终点的最短路径问题-即已知起点和

终点，求两结点之间的最短路径．

④全局最短路径问题-求图中所有的最短路径．

【问题原型】“将军饮马”，“造桥选址”，“费

马点”．

【涉及知识】“两点之间线段最短”，“垂线段最

短”，“三角形三边关系”，“轴对称”，“平

欧阳音创编2021.03.11欧阳音创编

2021.03.11

欧阳音创编2021.03.11欧阳音创编

2021.03.11

移”．

【出题背景】角、三角形、菱形、矩形、正方形、

梯形、圆、坐标轴、抛物线等．

【解题思路】找对称点实现“折”转“直”，近两

年出现“三折线”转“直”等变式问题考查．

【十二个基本问题】

【问题1】作法图形原理

A连AB，与l交点即为A两点之间线段最短．

在直线l上求一点P，使

P．PA+PB最小值为AB

PA+PB值最小．

lP

【问题2】“将军饮马”作法图形l原理

B作B关于l的对称点B＇

B两点之间线段最短．

在直线l上求一点P，使连AB＇，与l交点即为

AAPA+PB最小值为AB＇

PA+PB值最小．P．

BB

【问题3】l作法图形原理

l

分别作点P关于两直线P

两点之间线段最短．

在直线l、l上分别求点的对