(
课件网) 第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、迪杰斯特拉算 ... ...
