资源简介

(共16张PPT)
主题活动：最快路径
赣科学技术版五年级下册
第9课
主题活动：最快路径
(1)知道狄克斯特拉算法的步骤
(2)学会使用狄克斯特拉算法找到最快路径
任务卡
一
说一说
假设某书店某一类书籍6个种类的日销量数分别为15,6,24,18,30,9
册。现在要对这些书籍按销量从小到大进行排序。
问题
一
想一想
除了上节课的排序，还有没有其他的排序方法对其进行排序呢
请说出你的想法。
一
想一想
假设你想从起点A 处去终点D 处，如图所示，每个数字表示的都是时间，单位为分钟。请你找出从起点到终点所用时间最短的路线。
一
想一想
是不是途经路段最少，就有可能使所用时间最短呢 假设从节点A 出发，经节点 B, 到节点 D, 该路线使用了2条路段，所用时间7分钟，如图所示。A→B→D 这条路线所用时间是7分钟，还能否找到所用时间更短的路径呢!
二
试一试
前往节点B需要6分钟，前往节点C 需要2分钟，假设前往终点D 需要无穷大。因 此节点C 是最近的。
第一步：
找出最短路径节点。假设你站在节点A, 不知道该前往节点 B还是前往节点 C, 就比较前往这两个节点的所用时间时长，如图所示。
二
试一试
同样是从节点A 前往节点B, 直接过去所用时间6分钟，经节点C, 所用时间只需要5分钟。
第二步：
计算经节点 C前往其他各节点所需要的时间，如图所示。
二
试一试
重复以上步骤，请把接下来的步骤示意图画在书本42页方框中。
第三步：
重复第一步：找出可在最短时间内前往终点D 的路线。对节点C 执行了第二步，除节点C外，可在最短时间内前往的节点是节点B。
重复第二步：更新节点C 的所有节点的所用时间，发现前往终点D 的时间为6分钟!
前往节点C 需要2分钟；
前往节点B需要5分钟；
前往终点D需要6分钟。
二
试一试
最终路线：A→C→B→D,最快时间：2+3+1=6分钟。
第四步：
计算最终路线所用时间。
三
评一评
请根据本次动手实践情况，在表中相应的位置涂“☆”。(“非常好”涂☆☆☆ ☆☆,“好”涂☆☆☆,“还需努力”涂☆)
评价内容 自评 互评 教师评
知道狄克斯特拉算法的具体步骤 ☆☆☆☆☆ ☆☆☆☆☆ ☆☆☆☆☆
能运用狄克斯特拉算法找到最快路径 ☆☆☆☆☆ ☆☆☆☆☆ ☆☆☆☆☆
能画出正确的最快路径图 ☆☆☆☆☆ ☆☆☆☆☆ ☆☆☆☆☆
总结狄克斯特拉算法的4个步骤。
练一练
谢谢聆听！
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
兼职招聘：
https://www.21cnjy.com/recruitment/home/admin

展开更多......

收起↑