数据结构：最短路径算法83页PPT

故 （AC+CD+DB）min
• 问题 5：如图，A，B两地在一条河的两岸，现要
在河上建一座桥MN，桥造在何处才能使从A到B的
路径最短？（假设河的两岸是平行的直线，桥要
与河垂直）
.A M
作法： 1、将点B沿垂直与河岸的方
向平移一个河宽到E
N
. E 2、连接AE交河对岸与点M,
则
.B
点M为建桥的位置，MN为
b
河 草地
. Pa
河 草地
• 作法：
1、作点P关于直线a的对称点
P2
b
P1，关于直线b对称点P2
B
2、连接P1P2，分别交直线
.P
a,b于点A，B 3、连接PA，PB，由对称轴的
A
a 性质知，PA= P1A，PB=P2B ∴先到点A处吃草，再到点B
P1
处饮水，最后回到营地，
这时的放牧路线总路程最
短，即 (PB+BA+AP)min
圆柱侧面展开图的宽1m处和长 24m的中点处，即AB长为最短
AB2 由AC勾2 股 B定C理2 得169
路线.(如图)
∴AB=13(m)
问题 7：如图，是一个三级台阶，它的每一级的长、
宽和高分别等于5cm，3cm和1cm，A和B是这个台阶的两
个相对的端点，A点上有一只蚂蚁，想到B点去吃可口
的食物.请你想一想，这只蚂蚁从A点出发，沿着台阶
处，它要沿着木块侧面爬到点D处，则
蚂蚁爬行的最短路径是
74 。
D
4
C
A
5
B3
• 2、现要在如图所示的圆柱体侧面A点与
B点之间缠一条金丝带（金丝带的宽度

《最短路径算法》PPT课 件
探索最短路径算法的奥秘，了解其在各领域中的应用，以及选择最佳算法的 依据，展望最短路径算法的未来。
最短路径算法简介
最短路径问题的定义和最短路径算法的广泛应用。
单源最短路径算法
1
贝尔曼-福德算法2 Nhomakorabea算法思想：通过利用松弛操作，逐步更新节 点之间的最短路径。
算法步骤：进行N-1次松弛操作，其中N为节 点数，再进行一次检查负权边。
电路板布线
通过最短路径算法规划电路板 上元件的布线路径，减小电路 的延迟，提高性能。
应用最短路径算法的问题探讨
1 负权边问题
2 负环问题
遇到边权值为负数的情况，部分最短路径算法需 要特殊处理。
当图中存在负权环时，部分最短路径算法无法得 到准确的最短路径。
最短路径算法总结
1 各种算法的优劣
不同最短路径算法在不同场景下有不同的优劣，需要根据具体情况进行选择。
算法复杂度分析：时间复杂度为O(V*E)，V 为节点数，E为边数。
迪杰斯特拉算法
算法思想：通过记录已知最短路径和待确认 节点，逐步更新最短路径。
算法步骤：从起点出发，不断更新最短路径， 直到所有节点都被确认为最短路径。
算法复杂度分析：时间复杂度为O(V^2)，V 为节点数。
多源最短路径算法
1
弗洛伊德算法
算法思想：通过动态规划，逐步更新节点间 的最短路径。
算法步骤：利用矩阵记录节点间最短路径， 逐步更新矩阵，得到所有节点的最短路径。
算法复杂度分析：时间复杂度为O(V^3)，V为 节点数。
最短路径算法的应用实例
地图导航
使用最短路径算法规划最佳行 驶路线，提供准确的导航指引。
网络路由

C
你能要自己的语言重新描述一下问题吗？ C是l上一个动点， 当点C在l的什么位置时，AC+BC最小？
探究 如图，点A，B 在直线l 的同侧，点C 是直线上的一个动点，当点C 在l 的什么位置时，AC 与CB 的和最小？
一开始的时候我们就讨论过点A，B在直线异侧的情况， 你还记得是怎么做的吗？ 连接两点，交点就是所求 同侧的情况也能直连接两点吗？不行
拓广探索
在纸上画五个点，使任意三个点组成的三角形都 是等腰三角形 . 这五个点应该怎样画？
拓广探索
如图，△ABC 是等边三角形，BD 是中线，延长BC 至 E，使CE =CD . 求证DB =DE .
拓广探索
如图，△ABC 是等腰三角形，AC =BC，△BDC 和△ACE 分别为等边三角形，AE 与BD 相较于F，连接CF 并延长 ，交AB 于点G . 求证：G 为AB 的中点 .
复习巩固
如图，在△ABC 中，∠ABC =50°，∠ACB =80°，延长 CB至D，使DB =BA，延长BC 至E，使CE =CA，连接 AD，AE .求∠D，∠E，∠DAE 的度数 .
复习巩固 如图，AD =BC，AC=BD，求证：△EAB 是等腰三角形 .
复习巩固
综合应用
试确定如图所示的正多边形的对称轴的条数，一般地 ，一个正n边形有多少条对称轴？
综合应用
如图，从图形Ι 到图形Ⅱ是进行了平移还是轴对称？如果 是轴对称，找出对称轴；如果是平移，是怎样平移？
综合应用
如图，AD是△ABC 的角平分线，DE，DF 分别是△ABD 和△ACD的高 . 求证：AD 垂直平分EF .
综合应用
如图，在等边三角形 ABC 的三边上，分别取点D，E，F ，使AD =BE =CF . 求证△DEF 是等边三角形 .

13.4 课题学习 最短路径问题
导入新课
讲授新课
当堂练习
课堂小结
.
1
学习目标
1.体会图形的变化在解决最值问题中的作用，感悟转 化思想．（重点）
2.能利用轴对称解决简单的最短路径问题.（难点）
.
2
导入新课
复习引入 1.如图，连接A、B两点的所有连线中，哪条最短？为什么？
②最短，因为两点之间，线段最短
A．P是m上到A、B距离之和最短的
点，Q是m上到A、B距离相等的点
B．Q是m上到A、B距离之和最短的
点，P是m上到A、B距离相等的点
C．P、Q都是m上到A、B距离之和最
短的点
D．P、Q都是m上到A、B距离相等
的点
.
16
2.如图，∠AOB=30°，∠AOB内有一定点P，且
OP=10．在OA上有一点Q，OB上有一点R．若
△PQR周长最小，则最小周长是（ A ）
A．10
B．15
C．20
D．30
.
17
3.如图，牧童在A处放马，其家在B处，A、B到河岸的距离分 别为AC和BD，且AC=BD,若点A到河岸CD的中点的距离为500 米，则牧童从A处把马牵到河边饮水再回家，所走的最短距离 是 1000 米.
C
D 河
A
B
.
18
则点C 即为所求． ACΒιβλιοθήκη B lB′.
9
问题3 你能用所学的知识证明AC +BC最短吗？
证明：如图，在直线l 上任取一点C′（与点C 不重合），
连接AC′，BC′，B′C′．由轴对称的性质知，
BC =B′C，BC′=B′C′．
∴ AC +BC= AC +B′C = AB′，

点，该值为无穷大） ➢ distTo[v]是最短路径，当且仅当：对于任意一条v到w的边e，都满足：
distTo[w] ≤ distTo[v] + e.weight()
最短路径通用算法
• 算法SP(G， s)：
➢ distTo[s] 初始化为 0 ➢ 对于其他各个节点， distTo[v]初始化为无穷大 ➢ 重复如下操作：松驰G中的任意边，直到不存在有效边为止
顶点0 0 0
顶点0 0 0
顶点0 0 0
顶点1 -
顶点1 10 0->1
顶点1 10 0->1
顶点1 10 0->1
顶点1 10 0->1
顶点2 -
顶点3 -
顶点2 60，50 1->2, 3->2
顶点3 30 0->3
顶点2 50 3->2
顶点3 30 0->3
顶点2 50 3->2
顶点2 50 3->2
算法与数据结构
最短路径
目录
最短路径介绍 Dijkstra算法 Bellman Ford算法
最短路径问题
• 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终 点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的 权值总和达到最小。（有向带权图）
• 问题解法
➢ 边上权值非负情形的单源最短路径问题 （s -> 图上其他节点的最短路径）
10 0
1
30
50 2 20
100 10 4
60 3
➢distTo[0] = 0
➢distTo[1] = 10 ➢distTo[2] = 50 ➢distTo[3] = 30 ➢distTo[4] = 90

第十三章 轴对称
故事引入
导入新课
复习旧知
1.如图，连接A、B两点的所有连线中，哪条最短？
①
为什么？
②
②最短，因为两点之间，线段最短
A ③B
2.如图，点P是直线l外一点，点P与该直线l上各点连
接的所有线段中，哪条最短？为什么？
P
PC最短，因为垂线段最短
A BC
Dl
3.如图，如何作点A关于直线l的对称点？
B
A
C
l
联想旧知
B
A
C
l
B′
用旧知解决新知
A
C
l
B
提示：本题也可作A点关于直线l的对称点
典例精析
例1 如图，已知点D、点E分别是等边三角形ABC
中BC、AB边的中点，AD=5，点F是AD边上的动
点，则BF+EF的最小值为（ B ）
A．7.5
B．5
C．4
D．不能确定
解析：△ABC为等边三角形，点D是BC边的中点，即点B与点 C关于直线AD对称.∵点F在AD上，故BF=CF.即BF+EF的最小 值可转化为求CF+EF的最小值，故连接CE即可，线段CE的长 即为BF+EF的最小值.
l2
l2
2.关键： 作对称点，利用轴对称的性质将线段转化， 从而利用“两点之间，线段最短”来解决
作法及思路分析
1.作点A关于直线 l 的对称点A′ ，连接CA′。
B A
l
C
A′
2.由上步可知AC+CB=B_′_A_C_+_C_B_′ ___
思考：当C在直线 l 的什么位置时AC +CB′最短？
3.如图，如何作点A关于直线l的对称点？

这种算法最关键的问题就是如何确定估价函数，估价函数越准，则能 越快找到答案。这种算法实现起来并不难，只不过难在找准估价函数，大 家可以自已找相关资料学习和思考。
.
3
最短路径问题的求解
三、等代价搜索法 等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与
启发式搜索的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之 处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值， 也就是说，等代价搜索法是启发式搜索的一种简化版本。它的大体思路是：
.
2
最短路径问题的求解
二、 启发式搜索 在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开，
而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开 的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答 案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。
.
12
最短路径问题的求解
八、Dijkstra算法（从一个顶点到其余各顶点的最短路径，单源最短路径） 例3、如下图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两 城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到Ci 的最短路径(2≤i≤6)，输出路径序列及最短路径的路程长度。
3、由数轴可见，A与A'点相比，A点离原点近，因而保留A点，删除A'点，相应的，B、B'点保留B点， D、D'保留D'，E、E'保留E'，得到下图：
.
11
最短路径问题的求解
4、此时再以离原点最近的未展开的点B联接的所有点，处理后，再展开离原点最近未展开的D点， 处理后得到如下图的最终结果：

50 10 60 edgeTo[3] = 0，反过来排列，
2 20 3
得到路径 0, 3, 2, 4，这就是源 点0到终点4的最短路径。
Dijkstra示例
顶点0 0 0
顶点1 -
顶点2 -
顶点3 -
顶点4 -
索引堆：
0
10 0 100
1 30 4
50 10
60
2 20 3
0
1
2
3
4
0
-
-
-
-
Dijkstra示例
短路径长度； ➢ ...... ➢ dist n-1 [u]为从源点s出发最多经过不构成负权值回路的n-1次relax到达终点u的
最短路径长度；
• 算法的最终目的是计算出dist n-1 [u]，为源点v到顶点u的最短 路径长度。
dist k [u]的计算
• 设已经求出 dist k-1 [u] , u = 0, 1, …, n-1，即从源点s经过最多 不构成负权值回路的k-1次relax到达终点u的最短路径的长度
点，该值为无穷大） ➢ distTo[v]是最短路径，当且仅当：对于任意一条v到w的边e，都满足：
distTo[w] ≤ distTo[v] + e.weight()
最短路径通用算法
• 算法SP(G， s)：
➢ distTo[s] 初始化为 0 ➢ 对于其他各个节点， distTo[v]初始化为无穷大 ➢ 重复如下操作：松驰G中的任意边，直到不存在有效边为止
➢ dist 1 [u]为从源点s到终点u的最多经过1次relax的最短路径长度，并有dist 1 [u] =adj[s][u]；
➢ dist 2 [u]为从源点s最多经过两次relax到达终点u的最短路径长度； ➢ dist 3 [u]为从源点s出发最多经过不构成负权值回路的三次relax到达终点u的最

12
图论及其应用 作业 用Dijkstra算法求出下图中从顶点a到其它所有 顶点的最短路径及及长度。
13
图论及其应用
有向图中求最短路径的Dijkstra算法
设Sj是带权有向图G中自顶点1到顶点j的最短有向路的长度 步骤1：置P={1}，T={2,3,…,n}且S1=0，Sj=w1j， j=2,3,…,n 。 步骤2：在T中寻找一点k，使得Sk=min{Sj}，置P=P{k}， T=T- {k}。若T=，终止；否则，转向步骤3。 步骤3：对T中每一点j，置Sj=min {Sj ，Sk+ wkj}，然后转向步 骤2。 算法经过n-1 次循环结束。
6
1-6-8-B
6-8-B
13
10
5
图论及其应用
指定点到其它所有点的最短路径
解决这一问题最著名的方法是 Dijkstra算法，这个算法是由荷 兰计算机科学教授Edsger W.Dijkstra在1959年提出的。 他在1972年获得美国计算机协 会授予的图灵奖，这是计算机 科学中最具声望的奖项之一。
最终，起点上方的最短路线及权值即为起点到终点的最 短路线及长度。
3
图论及其应用
例 使用回溯法求下图中结点1到结点10的最短路径
2-6-9-10 600
1-4-6-9-10 650
4-6-9-10 500
6-9-10
300
9-10
100 5-8-10
400
8-10
150
3-5-8-10 600
7-8-10 275
定义2 已知矩阵A=(aij)m n ，B =(bij)mn，规定C=AB=(dij)mn，
其中dij=min(aij, bij)

将A，B 两地抽象为两个点，将河l 抽象为一条直 线．
·B A·
l
探索新知
追问2 你能用自己的语言说明这个问题的意思， 并把它抽象为数学问题吗？
（1）从A 地出发，到河边l 饮马，然后到B 地； （2）在河边饮马的地点有无穷多处，把这些地点与A，
B 连接起来的两条线段的长度之和，就是从A 地 到饮马地点，再回到B 地的路程之和；
若直线l 上任意一点（与点 C 不重合）与A，B 两点的距离 和都大于AC +BC，就说明AC + BC 最小．
A
·
C′ C
B
·
l
B′
探索新知
追问2 回顾前面的探究过程，我们是通过怎样的 过程、借助什么解决问题的？
A
·
C′ C
B
·
l
B′
为深入学习习近平新时代中国特色社 会主义 思想和 党的十 九大精 神,贯彻 全国教 育大会 精神,充 分发挥 中小学 图书室 育人功 能
(Ⅰ)两点在一条直线异侧
已知：如图，A，B在直线L的两侧， 在L上求一点P，使得PA+PB最小。
连接AB,线段AB与直线L的交点P ，就是所求。
P
为深入学习习近平新时代中国特色社 会主义 思想和 党的十 九大精 神,贯彻 全国教 育大会 精神,充 分发挥 中小学 图书室 育人功 能
思考？？？
为什么这样做就能得到最短距 离呢？
根据：两点之间线段最短.
引入新知
引言： 前面我们研究过一些关于“两点的所有连线中，线 段最短”、“连接直线外一点与直线上各点的所有线段 中，垂线段最短”等的问题，我们称它们为最短路径问 题．现实生活中经常涉及到选择最短路径的问题，本节 将利用数学知识探究数学史中著名的“将军饮马问题”．