B 7 D 12 A 5 4 3 C 6 E 位置 A B ⊙ D E A 0 12 3 999 999 B……12……0…… 7… .999.…… C 3 5 日 999 6 D 999 7 999 0 4 E 999 999 6 4 0 B 7 D 12 位置 A B D E A 0 12 3 999 999 A B…20…③ 7… …999… 5 4 C 3 5 ⑤ 999 6 3 D 999 7 999 0 4 E 999 999 4 0 6 E 路线模型图 数据表 B 7 D 12 A 5 12 4 3 C 6 E 位置 A B C D E A B C D E B 7 D 12 A 5 12 4 3 C 6 E(
课件网) 信息科技五年级下册 单元主题七 ：快递路线规划师 活动2：最短路径的算法 授课教师： 情境导入———快递员小李的烦恼 快递员小李在大家的帮助下，快递派送的非常快，受到了附近村民的一致称赞。勤劳的小李想拓展业务，多负责几个村的快递派送。但是如何在复杂的地图中快速找到最短路径呢？ 在路线相对简单的情况下，使用上节课我们学习的穷举法来寻找最短路径是可行的方法。但如果要在复杂路线中寻找最短路径，还需要更有效的方法和计算机的帮助。 情境导入 聪明的人类可以很快读懂路线图，计算机是怎么读图的？计算机是如何寻找最短路径的？ A B C D E 12 5 7 4 3 6 任务一 用数据表格表示路线图 计算机处理图相关的问题需要先将图转化为数据表。 位置 A B C D E A 0 12 3 999 999 B 12 0 5 7 999 C 3 5 0 999 6 D 999 7 999 0 4 E 999 999 6 4 0 数据表 路线模型图 思考分析：请观察路线模型图与数据表，思考数据表中的下列数据表示的具体含义。 任务一 用数据表格表示路线图 1.交叉点数值“5”表示两点 点和 点的直接连接距离。 2.“0”表示 的距离。 3.如果两点没有直接连通的路线，可以用一个很大的数，比如表中的 ，表示这两点间的距离。 4.不考虑方向因素，AB与BA之间路线的距 离 ，所以表格中黄色和蓝色部分 。 B C 某点自己到自己 999 相同 对称 任务一 用数据表格表示路线图 讨论交流：尝试去掉表格中含义相同的数据，将数据进一步简化。 AB=12 AC=3 AD=999 AE=999 BC=5 BD=7 BE=999 CD=999 CE=6 DE=4 任务二 迪杰斯特拉算法 要帮助快递员寻找配送快递的最短路径，可以采用迪杰斯特拉算法（Dijkstra），计算从A点出发，去到B、C、D、E各地点配送快递的最短路径，具体步骤描述如下。 任务二 迪杰斯特拉算法 1.设置初始状态 （1）设计两个方框，分别保存已找到的最短路径和当前发现的路线。 最短路径 当前发现的路线 （2）列举从起点A开始，与起点A相关的路线并放入橙框。 AB=12 AC=3 AD=999 AE=999 任务二 迪杰斯特拉算法 2.寻找第一条最短路径 （1）对橙框里的路线排序。 最短路径 当前发现的路线 （2）将最短的路线移入蓝框。 AB=12 AD=999 AE=999 （3）确定第一条最短路径为AC=3。 AC=3 任务二 迪杰斯特拉算法 3.寻找第二条最短路径 （1）重新计算路径长度。 计算起点A通过已知最短路径“AC=3”到达其他点的长度。 最短路径 当前发现的路线 （2）比较新路径与原路径，用更短的新路径代替原路径。 ACD=AC+CD=3+999=1002 （3）将橙框中的最短路径移到蓝框中,选出第二条最短路径为ACB=8。 AD=999 AE=999 AB=12 ACB=AC+CB=3+5=8 ACE=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=999 ACE=9 ACBE=ACB+BE =8+999=1007 不换 替换 < > AC=3 ACB=8 新路径 任务二 ... ...
