资源简介

(共34张PPT)
第7单元 第2课
最短路径的算法
（湘科版）五年级
下
1
核心素养目标
3
新知讲解
5
拓展延伸
7
板书设计
2
新知导入
4
课堂练习
6
课堂总结
课后作业
8
01
核心素养目标
信息意识
计算思维
数字化学习与创新
信息社会责任
学会在使用算法和处理数据时，考虑到社会责任和道德问题， 探讨算法的社会影响，思考怎样让技术更好地服务于社会。
编写程序的过程中，提升数字化技能，探索算法应用的创新可能性，编程完成后，思考其他可以应用这个算法的领域。
学习迪杰斯特拉算法，理解它的步骤，提升解决问题的能力，亲自动手解决从一个地方到另一个地方的最短路径问题。
理解生活中常见问题如何通过算法解决，能把地图转成数据表，尝试用数据去描述一个城市的道路网络。
02
新知导入
活动背景
在路线相对简单的情况下，用穷举法来寻找最短路径是可行的方法。但如果要在复杂路线中寻找最短路径，还需要更有效的方法和计算机的帮助。
02
新知导入
活动目标
1、学会用数据表格表示路线图。
2、了解迪杰斯特拉算法的实现过程。
3、体验迪杰斯特拉算法的程序实现。
02
新知导入
03
新知讲解
一、用数据表格表示路线图
计算机无法像人一样直接读懂图，为了处理图的相关问题，需要先将图转化为数据表。如左图所示的路线模型图，可以转换为如右图所示的数据表。
03
新知讲解
由于不考虑方向的因素，观察表格中的数据可以发现，AB与BA之间路线的距离相同,以此类推。所以,表格中黄色部分的数据与蓝色部分对称。数据可以进一步简化为：
AB=12 AC=3 AD=999 AE=999
BC=5 BD=7 BE=999
CD=999 CE=6
DE=4
03
新知讲解
二、迪杰斯特拉算法
要帮助快递员寻找配送快递的最短路径，可以采用迪杰斯特拉算法(Diikstra)，计算从A点出发，去到B、C、D、E各地点配送快递的最短路径，具体步骤描述如下。
1、设置初始状态。设计两个方框，分别保存已找到的最短路径和当前发现的路线。从起点A开始，将与起点A相关的路线放入橙框。
03
新知讲解
2、寻找第一条最短路径。
（1）对橙框里的路线排序。
（2）将最短的路线移入蓝框。
（3）找到第一条最短路径。
03
新知讲解
3、寻找第二条最短路径步骤。
步骤1：重新计算路径长度。计算起点A通过已知最短路径“AC=3”到达其他点的长度。
03
新知讲解
步骤2：比较新路径与原路径，用更短的新路径代替原路径。
03
新知讲解
步骤3：将橙框中的最短路径移到蓝框中。选出第二条最短路径。
03
新知讲解
步骤4：按照同样的方法，继续寻找其余最短路径，直到橙框里的路径为空。
到此，找到从起点 A到其余四点 B、C、D、E 的最短路径。
03
新知讲解
从起点A到目的点D的最短路径是A→C→E→D，长度为13。观察并验证这个结论。
探究实践
03
新知讲解
用迪杰斯特拉算法寻找最短路径的过程可以概括为:
03
新知讲解
尝试求解下图中从A点到其余各点的最短路径。
探究实践
03
新知讲解
尝试求解下图中从A点到其余各点的最短路径。
探究实践
目标节点 最短路径 总距离
A A 0
B A → C → B 8
C A → C 3
D A → C → E → D 13
E A → C → E 9
03
新知讲解
三、迪杰斯特拉算法的程序实现
人工推算最短路径的方法效率低，易出错。通过计算机编程实现算法可以快速运算出结果，极大地提高效率，解决更复杂的路径查找问题。
03
新知讲解
使用计算软件寻找最短路径。
步骤1：将路线图用数据表格表示。
探究实践
03
新知讲解
步骤2：将数据输入计算机，计算最短路径。
探究实践
步骤3：在路线图上验证答案。
04
课堂练习
一、选择题
1、简化后的数据表格中，AB=12，BA=12，这是因为（ ）
A. 路线是单向的 B. 路线是双向的
C. 表格填写错误 D. 需要对称美观
2、迪杰斯特拉算法中，初始步骤需要将哪个点的相关路线放入橙框？（ ）
A. 终点 B. 起点
C. 中间点 D. 任意点
3、在迪杰斯特拉算法中，橙框中的路线排序规则是（ ）
A. 从长到短 B. 从短到长
C. 随机排序 D. 按字母顺序
B
B
B
04
课堂练习
4、重新计算路径长度时，需要基于（ ）
A. 所有可能的路线 B. 已找到的最短路径
C. 未探索的路线 D. 随机选择的路线
5、迪杰斯特拉算法特别适合解决（ ）
A. 简单路线问题 B. 复杂路线的最短路径
C. 路线颜色标记 D. 快递包裹重量
二、判断题
数据表格简化后，可以随意删除任意一半的数据。（ ）
B
×
B
04
课堂练习
三、操作题
路径转化
将下图路线模型转化为数据表格：
A—B=5, A—C=2, B—D=8, C—D=4
A B C D
A 0 5 2 999
B 5 0 999 8
C 2 999 0 4
D 999 8 4 0
05
拓展延伸
常见最短路径算法
除了迪杰斯特拉算法之外，还有很多类似的最短路径算法，如:弗洛伊德算法、贝尔曼-福特算法(Bellman-Ford)和 SPFA 算法等。这些算法各有特点，可满足不同的需要。在现实生活中，最短路径算法的应用非常广泛，比如手机导航、城市道路规划和网络通信等。
05
拓展延伸
生活中的导航小助手
手机地图如何帮你找到最近的路？它其实用了类似迪杰斯特拉的算法，实时计算道路距离和拥堵情况，像一位隐形向导帮你规划最优路线！
05
拓展延伸
迷宫游戏的秘密路径
玩迷宫时如何快速找到出口？试试“贴墙法”或“最短步数法”，这和计算机寻找最短路径的思路很像，都是通过不断尝试和排除错误选项。
出口
入口
05
拓展延伸
快递小哥的智慧派送
快递公司如何安排送货顺序？他们用算法计算最短路线，减少时间和油耗，下次收到快递时，可以想想背后的“数学魔法”哦！
05
拓展延伸
算法背后的科学家故事
迪杰斯特拉算法的发明者艾兹赫尔·戴克斯特拉（Edsger Dijkstra）是一位荷兰计算机科学家，他最初设计这个算法是为了解决铁路网络的优化问题。
06
课堂总结
1
引入新知内容
最短路径的算法
2
用数据表格表示路线图
3
迪杰斯特拉算法
4
迪杰斯特拉算法的程序实现
5
进行相关知识拓展
1
2
3
4
5
07
板书设计
最短路径的算法
1、进行新知引入
2、用数据表格表示路线图
3、迪杰斯特拉算法
4、迪杰斯特拉算法的程序实现
5、进行知识拓展
课后作业。
1、上网查找资料，了解用弗洛伊德算法(Floyd)求解最短路径的基本过程。
08
课后作业
1、如果两点间用一个很大的数来表示路线长度，说明 。
2、上网查找资料，了解用弗洛伊德算法(Floyd)求解最短路径的基本过程。
用弗洛伊德算法找最短路径的过程，就像玩一个“找近路”的游戏，分三步走：
（1）画表格：记录所有路线的长度 。先画一个表格，写下每个点到其他点的直接距离（比如：A到B是5，没直接路就写∞）。
（2）选中间人：试试“绕道走”会不会更近。比如，现在选一个中间点C，看看：从A到B，是直接走快？还是先到C，再从C到B更快？如果绕道更近，就更新表格里的距离！
（3）重复换中间人，直到试完所有人。
表示道路封闭或不可通行
https://www.21cnjy.com/recruitment/home/fine

展开更多......

收起↑