資源簡介

(共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

展開更多......

收起↑