湘科版（2024）五下_7单元_活动2 最短路径的算法 教学课件.pptxVIP

信息科技五年级下册单元主题七：快递路线规划师活动2：最短路径的算法授课教师：

情境导入——快递员小李的烦恼快递员小李在大家的帮助下，快递派送的非常快，受到了附近村民的一致称赞。勤劳的小李想拓展业务，多负责几个村的快递派送。但是如何在复杂的地图中快速找到最短路径呢？在路线相对简单的情况下，使用上节课我们学习的穷举法来寻找最短路径是可行的方法。但如果要在复杂路线中寻找最短路径，还需要更有效的方法和计算机的帮助。

情境导入聪明的人类可以很快读懂路线图，计算机是怎么读图的？计算机是如何寻找最短路径的？ABCDE1257436

任务一用数据表格表示路线图计算机处理图相关的问题需要先将图转化为数据表。位置ABCDEA01239999993509996D999799904E999999640数据表路线模型图

思考分析：请观察路线模型图与数据表，思考数据表中的下列数据表示的具体含义。任务一用数据表格表示路线图1.交叉点数值“5”表示两点点和点的直接连接距离。2.“0”表示的距离。3.如果两点没有直接连通的路线，可以用一个很大的数，比如表中的，表示这两点间的距离。4.不考虑方向因素，AB与BA之间路线的距离，所以表格中黄色和蓝色部分。BC某点自己到自己999相同对称

任务一用数据表格表示路线图讨论交流：尝试去掉表格中含义相同的数据，将数据进一步简化。AB=12AC=3AD=999AE=999BC=5BD=7BE=999CD=999CE=6DE=4

任务二迪杰斯特拉算法要帮助快递员寻找配送快递的最短路径，可以采用迪杰斯特拉算法（Dijkstra），计算从A点出发，去到B、C、D、E各地点配送快递的最短路径，具体步骤描述如下。1.设置初始状态2.寻找第一条最短路径3.寻找第二条最短路径

任务二迪杰斯特拉算法1.设置初始状态（1）设计两个方框，分别保存已找到的最短路径和当前发现的路线。最短路径当前发现的路线（2）列举从起点A开始，与起点A相关的路线并放入橙框。AB=12AC=3AD=999AE=999

任务二迪杰斯特拉算法2.寻找第一条最短路径（1）对橙框里的路线排序。最短路径当前发现的路线（2）将最短的路线移入蓝框。AB=12AD=999AE=999（3）确定第一条最短路径为AC=3。AC=3

任务二迪杰斯特拉算法3.寻找第二条最短路径（1）重新计算路径长度。计算起点A通过已知最短路径“AC=3”到达其他点的长度。最短路径当前发现的路线（2）比较新路径与原路径，用更短的新路径代替原路径。ACD=AC+CD=3+999=1002（3）将橙框中的最短路径移到蓝框中,选出第二条最短路径为ACB=8。AD=999AE=999AB=12ACB=AC+CB=3+5=8ACE=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=999ACE=9ACBE=ACB+BE=8+999=1007不换替换AC=3ACB=8新路径

任务二迪杰斯特拉算法5.按同样的方法继续寻找第四条最短路径。（1）重新计算路径长度。计算起点A通过已知最短路径“ACE=9”到达其他点的长度。最短路径当前发现的路线（2）比较新路径与原路径，用更短的新路径代替原路径。A