12.最短路径轻松找（教学课件）-五年级信息科技上册同步教学（泰山版2024）

第12课 最短路径轻松找 泰山版2024 五年级上册 第2单元 智慧校园用算法 1 趣味导入 要从教学楼到湖心岛游玩，要走哪条路呢？ 2 趣味导入 这么多条路，如何找到最短路径呢？ 3 趣味导入 只要找到从教学楼到各个地方的最短路径就好了。 4 放学后，同学们相约去湖心岛游玩，有多条路径供选择，要设计从教学楼到湖心岛的最短路径算法，需要哪些步骤？请用你喜欢的方式进行描述。 做中学 步骤1：________________________________________________ 步骤2：________________________________________________ 步骤3：________________________________________________ 放学后，同学们相约去湖心岛游玩，有多条路径供选择，要设计从教学楼到湖心岛的最短路径算法，需要哪些步骤？请用你喜欢的方式进行描述。 做中学 步骤1：________________________________________________ 步骤2：________________________________________________ 步骤3：________________________________________________ 分别标注两个地方之间的距离 计算从教学楼岛湖心岛的所有路径长度 找出所有路径中最短路径 最短路径是指一个点到其他点的最短“路径”，这里“路径”的数值可以指距离、时间、费用等。 做中学 思维导航 做中学 做中学 设起点教学楼为①，每个目的地先用数字表示，中间用线连接，并把长度标在上面。问题就转换为求起点①到②③④3个点的最短路径。 做中学 求①到其他点的最短距离，构造一个列表记录到②③④3个点的路 径距离。 做中学 求①到其他点的最短距离，构造一个列表记录到②③④3个点的路 径距离。 做中学 约定 1.如果①节点能够直接到达某节点，则路径长度即为其距离。 2.如果①节点不能直接达到某节点，则使用“无路”表示①到该点距离。 3.任何点到自身都为 0。 做中学 在最开始时，①点到图中所有点的距离列表如下： 做中学 第一次计算：首先选取该最短路径列表中值最小的一个点①，距离为 0。从剩下的点中选择距离最短的一个是①-④，距离为 s4=2。不需 要更新表格。 做中学 第二次计算： ①-②的距离为6 ①-④-②的距离为 s4+s3=5 更新①-②的距离为5 做中学 第二次计算： ①-③的距离为“无路” ①-④-③的距离为 s4+s5=11 更新①-③的距离为 11 做中学 第二次计算： 从剩下的点中选择最短的一个是①-④-② 做中学 第三次计算： ①-④-③的距离为 s4+s5=11 ①-④-②-③的距离为 s4+s3+s2=10 做中学 从①到各点的路线为: 做中学 N-S图 迪杰斯特拉算法思想是从最短距离列表中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。 小秘笈 做中学 已经选取过的点就是确定了最短路径的点，不再参与下一次计算。 小秘笈 做中学 练一练 请计算下图中①到④的最短路径。 练一练 能能正在成长林的入口，林中有许多条路，他选择了其中一条，找到了大强，请问在寻找大强的过程中，能能路过了下面哪些树? 练一练 擦线法是指把能够到达另外一点的较长的线擦除，直到找到最短路径为止的方法。 知识拓展 擦线法找最短路径 知识拓展 用擦线法寻找①→③最短路径的过程为: 从①到②: ①-②距离为 6 ①-④-②距离为5 ①-②不是最短路径，①-②这条线擦除 知识拓展 用擦线法寻找①→③最短路径的过程为: 从④到③: ④-③距离为 9 ④-②-③距离为 8 ④-③这条线擦除 知识拓展 用擦线法寻找①→③最短路径的过程为: 得到的唯一通路①-④-②-③ 即为所求最短路径。 30 $$