中小学教育资源及组卷应用平台 第2课《最短路径的算法》教学设计 课题 最短路径的算法 单元 第七单元 学科 信息科技 年级 五年级下 核心素养目标 信息意识：理解生活中常见问题如何通过算法解决，能把地图转成数据表，尝试用数据去描述一个城市的道路网络。计算思维：学习迪杰斯特拉算法，理解它的步骤，提升解决问题的能力，亲自动手解决从一个地方到另一个地方的最短路径问题。数字化学习与创新：编写程序的过程中，提升数字化技能，探索算法应用的创新可能性，编程完成后，思考其他可以应用这个算法的领域。信息社会责任：学会在使用算法和处理数据时，考虑到社会责任和道德问题， 探讨算法的社会影响，思考怎样让技术更好地服务于社会。 教学重点 1、学会用数据表格表示路线图。2、了解迪杰斯特拉算法的实现过程。 教学难点 1、掌握迪杰斯特拉算法的程序实现。 教学过程 教学环节 教师活动 学生活动 设计意图 导入新课 板书课题。活动背景在路线相对简单的情况下，用穷举法来寻找最短路径是可行的方法。但如果要在复杂路线中寻找最短路径，还需要更有效的方法和计算机的帮助。活动目标1、学会用数据表格表示路线图。2、了解迪杰斯特拉算法的实现过程。3、体验迪杰斯特拉算法的程序实现。观看教学视频《最短路径查找—Dijkstra算法》。 学习新知引入，观看教学视频。 用提问的方式引入课题，增强课堂互动性。将学生的注意吸引到课堂。 讲授新课 新知讲解：一、用数据表格表示路线图计算机无法像人一样直接读懂图，为了处理图的相关问题，需要先将图转化为数据表。如左图所示的路线模型图，可以转换为如右图所示的数据表。由于不考虑方向的因素，观察表格中的数据可以发现，AB与BA之间路线的距离相同,以此类推。所以,表格中黄色部分的数据与蓝色部分对称。数据可以进一步简化为。二、迪杰斯特拉算法要帮助快递员寻找配送快递的最短路径，可以采用迪杰斯特拉算法(Diikstra)，计算从A点出发，到B、C、D、E各地点配送快递的最短路径，具体步骤描述如下。1、设置初始状态。设计两个方框，分别保存已找到的最短路径和当前发现的路线。从起点A开始，将与起点A相关的路线放入橙框。2、寻找第一条最短路径。（1）对橙框里的路线排序。（2）将最短的路线移入蓝框。（3）找到第一条最短路径。3、寻找第二条最短路径步骤。步骤1：重新计算路径长度。计算起点A通过已知最短路径“AC=3”到达其他点的长度。步骤2：比较新路径与原路径，用更短的新路径代替原路径。步骤3：将橙框中的最短路径移到蓝框中。选出第二条最短路径。步骤4：按照同样的方法，继续寻找其余最短路径，直到橙框里的路径为空。探究实践从起点A到目的点D的最短路径是A→C→E→D，长度为13。观察并验证这个结论。用迪杰斯特拉算法寻找最短路径的过程可以概括为。探究实践尝试求解下图中从A点到其余各点的最短路径。三、迪杰斯特拉算法的程序实现人工推算最短路径的方法效率低，易出错。通过计算机编程实现算法可以快速运算出结果，极大地提高效率，解决更复杂的路径查找问题。探究实践使用计算软件寻找最短路径。步骤1：将路线图用数据表格表示。步骤2：将数据输入计算机，计算最短路径。步骤3：在路线图上验证答案。四、课堂练习。完成PPT22页到24页练习题。五、拓展延伸1、常见最短路径算法除了迪杰斯特拉算法之外，还有很多类似的最短路径算法，如:弗洛伊德算法、贝尔曼-福特算法(Bellman-Ford)和 SPFA 算法等。这些算法各有特点，可满足不同的需要。在现实生活中，最短路径算法的应用非常广泛，比如手机导航、城市道路规划和网络通信等。2、生活中的导航小助手手机地图如何帮你找到最近的路？它其实用了类似迪杰斯特拉的算法，实时计算道路距离和拥堵情况，像一位隐 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
