资源简介

B
7
D
12
A
5
4
3
C
6
E
位置
A
B
⊙
D
E
A
0
12
3
999
999
B……12……0……
7…
.999.……
C
3
5
日
999
6
D
999
7
999
0
4
E
999
999
6
4
0
B
7
D
12
位置
A
B
D
E
A
0
12
3
999
999
A
B…20…③
7…
…999…
5
4
C
3
5
⑤
999
6
3
D
999
7
999
0
4
E
999
999
4
0
6
E
路线模型图
数据表
B
7
D
12
A
5
12
4
3
C
6
E
位置
A
B
C
D
E
A
B
C
D
E
B
7
D
12
A
5
12
4
3
C
6
E(共23张PPT)
信息科技五年级下册
单元主题七 ：快递路线规划师
活动2：最短路径的算法
授课教师：
情境导入——快递员小李的烦恼
快递员小李在大家的帮助下，快递派送的非常快，受到了附近村民的一致称赞。勤劳的小李想拓展业务，多负责几个村的快递派送。但是如何在复杂的地图中快速找到最短路径呢？
在路线相对简单的情况下，使用上节课我们学习的穷举法来寻找最短路径是可行的方法。但如果要在复杂路线中寻找最短路径，还需要更有效的方法和计算机的帮助。
情境导入
聪明的人类可以很快读懂路线图，计算机是怎么读图的？计算机是如何寻找最短路径的？
A
B
C
D
E
12
5
7
4
3
6
任务一 用数据表格表示路线图
计算机处理图相关的问题需要先将图转化为数据表。
位置 A B C D E
A 0 12 3 999 999
B 12 0 5 7 999
C 3 5 0 999 6
D 999 7 999 0 4
E 999 999 6 4 0
数据表
路线模型图
思考分析：请观察路线模型图与数据表，思考数据表中的下列数据表示的具体含义。
任务一 用数据表格表示路线图
1.交叉点数值“5”表示两点 点和 点的直接连接距离。
2.“0”表示 的距离。
3.如果两点没有直接连通的路线，可以用一个很大的数，比如表中的 ，表示这两点间的距离。
4.不考虑方向因素，AB与BA之间路线的距 离 ，所以表格中黄色和蓝色部分 。
B
C
某点自己到自己
999
相同
对称
任务一 用数据表格表示路线图
讨论交流：尝试去掉表格中含义相同的数据，将数据进一步简化。
AB=12 AC=3 AD=999 AE=999
BC=5 BD=7 BE=999
CD=999 CE=6
DE=4
任务二 迪杰斯特拉算法
要帮助快递员寻找配送快递的最短路径，可以采用迪杰斯特拉算法（Dijkstra），计算从A点出发，去到B、C、D、E各地点配送快递的最短路径，具体步骤描述如下。
任务二 迪杰斯特拉算法
1.设置初始状态
（1）设计两个方框，分别保存已找到的最短路径和当前发现的路线。
最短路径
当前发现的路线
（2）列举从起点A开始，与起点A相关的路线并放入橙框。
AB=12
AC=3
AD=999
AE=999
任务二 迪杰斯特拉算法
2.寻找第一条最短路径
（1）对橙框里的路线排序。
最短路径
当前发现的路线
（2）将最短的路线移入蓝框。
AB=12
AD=999
AE=999
（3）确定第一条最短路径为AC=3。
AC=3
任务二 迪杰斯特拉算法
3.寻找第二条最短路径
（1）重新计算路径长度。
计算起点A通过已知最短路径“AC=3”到达其他点的长度。
最短路径
当前发现的路线
（2）比较新路径与原路径，用更短的新路径代替原路径。
ACD=AC+CD=3+999=1002
（3）将橙框中的最短路径移到蓝框中,选出第二条最短路径为ACB=8。
AD=999
AE=999
AB=12
ACB=AC+CB=3+5=8
ACE=AC+CE=3+6=9
替换
不换
替换
>
<
<
AC=3
新路径
ACB=8
任务二 迪杰斯特拉算法
探究实践：重复上述操作，继续寻找其余最短路径，直到橙框为空。
任务二 迪杰斯特拉算法
4.按同样的方法继续寻找第三条最短路径。
（1）重新计算路径长度。
计算起点A通过已知最短路径“ACB=8”到达其他点的长度。
最短路径
当前发现的路线
（2）比较新路径与原路径，用更短的新路径代替原路径。
ACBD=ACB+BD=8+7=15
（3）将橙框中的最短路径移到蓝框中,选出第三条最短路径ACE=9。
AD=999
ACE=9
ACBE=ACB+BE
=8+999=1007
不换
替换
<
>
AC=3
ACB=8
新路径
任务二 迪杰斯特拉算法
5.按同样的方法继续寻找第四条最短路径。
（1）重新计算路径长度。
计算起点A通过已知最短路径“ACE=9”到达其他点的长度。
最短路径
当前发现的路线
（2）比较新路径与原路径，用更短的新路径代替原路径。
ACED=ACE+ED=9+4=13
（3）将橙框中的最短路径移到蓝框中，选出第四条最短路径ACED=13。
AD=999
替换
<
AC=3
ACB=8
ACE=9
新路径
ACED=13
直到橙框里的路径为空，我们就找到了从起点A到其余四点B、C、D、E的最短路径。快递员小李可以按照下列路径送快递。
任务二 迪杰斯特拉算法
用迪杰斯特拉算法寻找最短路径的过程可以概括为：
任务二 迪杰斯特拉算法
讨论交流：从起点A到目的点D的最短路径是A→C→E→D，长度为13。
观察并验证这个结论。
探究实践：使用计算软件寻找最短路径。
步骤 1：将路线图用数据表格表示。
任务三 迪杰斯特拉算法的程序实现
探究实践：使用计算软件寻找最短路径。
步骤 2：将数据输入计算机，计算最短路径。
任务三 迪杰斯特拉算法的程序实现
步骤 3：在路线图上验证答案。
练习提升
1.如果两点间用一个很大的数来表示路线长度，说明 。
2.上网查找资料，了解用弗洛伊德算法（Floyd）求解最短路径的基本过程。
两点没有直接连通的路线
开拓视野
常见的最短路径算法
除了迪杰斯特拉算法之外，还有很多类似的最短路径算法，如：弗洛伊德算法、贝尔曼-福特算法（Bellman—Ford）和SPFA算法等。这些算法各有特点，可满足不同的需要。在现实生活中，最短路径算法的应用非常广泛，比如手机导航、城市道路规划和网络通信等。
课堂总结
本节课我们在“帮助快递员寻找配送快递的最短路径”这一真实问题情境驱动下，探索了借助迪杰斯特拉算法寻找最短路径的实现过程，并使用计算软件直观体验了迪杰斯特拉算法的程序实现。
生活中还有很多“最短路径算法”的应用场景，希望同学们能将算法思维代入真实问题情境，灵活使用迪杰斯特拉算法解决“求最短路径”的问题，并积极探索其他最短路径算法，思考不同算法的不同适用场景和优缺点。
课堂总结
课后练习
上网查找资料，分析下列常见的最短路径算法的适用场景和优缺点。
最短路径算法 适用场景 优点 缺点
迪杰斯特拉算法
弗洛伊德算法
贝尔曼-福特算法
SPFA算法
同学们，下节课再见！

展开更多......

收起↑