(完整word版)八年级最短路径问题归纳小结-推荐文档

八年级数学最短路径问题【问题概述】最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括：①确定起点的最短路径问题 - 即已知起始结点

八年级数学最短路径问题 【问题概述】 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结 点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题-即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题-求图中所有的最短路径． 【问题原型】 “将军饮马”，“造桥选址”，“费马点”． 【涉及知识】 “两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】 角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】 找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查． 十二个基本问题 【】 1 【问题】 作法 图形 原理 两点之间线段最短． ABlP 连，与交点即为． PAPBAB + 最小值为． lP 在直线上求一点，使 PAPB + 值最小． 2 【问题】 “将军饮马” 作法 图形 原理 BlB 作关于的对称点＇ 两点之间线段最短． ABl 连＇，与交点即为 PAPBAB + 最小值为＇． P ． lP 在直线上求一点，使 PAPB + 值最小． 3 【问题】 作法 图形 原理 P 分别作点关于两直线的 两点之间线段最短． PPP ＇＇， 对称点＇和连＇ PMMNPN ++ 的最小值为 PM ＇＇， 与两直线交点即为， PP ＇＇＇ 线段的长． N ． 、 在直线上分别求点 MNPMN 、，使△的周长 最小． 4 【问题】 作法 图形 原理 QP 分别作点、关于直线 两点之间线段最短． QP 、 ＇ 的对称点＇和 PQMN 四边形周长的最 QP ＇＇ 连，与两直线交点即 PP ＇＇＇ 小值为线段的长． MN 为，． 、 在直线上分别求点 -1-