第7單元第2課最短路徑的算法（湘科版）五年級(jí)下1核心素養(yǎng)目標(biāo)3新知講解5拓展延伸7板書(shū)設(shè)計(jì)2新知導(dǎo)入4課堂練習(xí)6課堂總結(jié)課后作業(yè)801核心素養(yǎng)目標(biāo)信息意識(shí)計(jì)算思維數(shù)字化學(xué)習(xí)與創(chuàng)新信息社會(huì)責(zé)任學(xué)會(huì)在使用算法和處理數(shù)據(jù)時(shí)，考慮到社會(huì)責(zé)任和道德問(wèn)題，

探討算法的社會(huì)影響，思考怎樣讓技術(shù)更好地服務(wù)于社會(huì)。編寫(xiě)程序的過(guò)程中，提升數(shù)字化技能，探索算法應(yīng)用的創(chuàng)新可能性，編程完成后，思考其他可以應(yīng)用這個(gè)算法的領(lǐng)域。學(xué)習(xí)迪杰斯特拉算法，理解它的步驟，提升解決問(wèn)題的能力，親自動(dòng)手解決從一個(gè)地方到另一個(gè)地方的最短路徑問(wèn)題。理解生活中常見(jiàn)問(wèn)題如何通過(guò)算法解決，能把地圖轉(zhuǎn)成數(shù)據(jù)表，嘗試用數(shù)據(jù)去描述一個(gè)城市的道路網(wǎng)絡(luò)。02新知導(dǎo)入活動(dòng)背景

在路線相對(duì)簡(jiǎn)單的情況下，用窮舉法來(lái)尋找最短路徑是可行的方法。但如果要在復(fù)雜路線中尋找最短路徑，還需要更有效的方法和計(jì)算機(jī)的幫助。02新知導(dǎo)入活動(dòng)目標(biāo)1、學(xué)會(huì)用數(shù)據(jù)表格表示路線圖。2、了解迪杰斯特拉算法的實(shí)現(xiàn)過(guò)程。3、體驗(yàn)迪杰斯特拉算法的程序?qū)崿F(xiàn)。02新知導(dǎo)入03新知講解一、用數(shù)據(jù)表格表示路線圖

計(jì)算機(jī)無(wú)法像人一樣直接讀懂圖，為了處理圖的相關(guān)問(wèn)題，需要先將圖轉(zhuǎn)化為數(shù)據(jù)表。如左圖所示的路線模型圖，可以轉(zhuǎn)換為如右圖所示的數(shù)據(jù)表。03新知講解

由于不考慮方向的因素，觀察表格中的數(shù)據(jù)可以發(fā)現(xiàn)，AB與BA之間路線的距離相同,以此類推。所以,表格中黃色部分的數(shù)據(jù)與藍(lán)色部分對(duì)稱。數(shù)據(jù)可以進(jìn)一步簡(jiǎn)化為：AB=12AC=3AD=999AE=999BC=5BD=7BE=999CD=999CE=6DE=403新知講解二、迪杰斯特拉算法

要幫助快遞員尋找配送快遞的最短路徑，可以采用迪杰斯特拉算法(Diikstra)，計(jì)算從A點(diǎn)出發(fā)，去到B、C、D、E各地點(diǎn)配送快遞的最短路徑，具體步驟描述如下。1、設(shè)置初始狀態(tài)。設(shè)計(jì)兩個(gè)方框，分別保存已找到的最短路徑和當(dāng)前發(fā)現(xiàn)的路線。從起點(diǎn)A開(kāi)始，將與起點(diǎn)A相關(guān)的路線放入橙框。03新知講解2、尋找第一條最短路徑。（1）對(duì)橙框里的路線排序。（2）將最短的路線移入藍(lán)框。（3）找到第一條最短路徑。03新知講解3、尋找第二條最短路徑步驟。步驟1：重新計(jì)算路徑長(zhǎng)度。計(jì)算起點(diǎn)A通過(guò)已知最短路徑“AC=3”到達(dá)其他點(diǎn)的長(zhǎng)度。03新知講解步驟2：比較新路徑與原路徑，用更短的新路徑代替原路徑。03新知講解步驟3：將橙框中的最短路徑移到藍(lán)框中。選出第二條最短路徑。03新知講解步驟4：按照同樣的方法，繼續(xù)尋找其余最短路徑，直到橙框里的路徑為空。到此，找到從起點(diǎn)A到其余四點(diǎn)B、C、D、E的最短路徑。03新知講解

從起點(diǎn)A到目的點(diǎn)D的最短路徑是A→C→E→D，長(zhǎng)度為13。觀察并驗(yàn)證這個(gè)結(jié)論。探究實(shí)踐03新知講解用迪杰斯特拉算法尋找最短路徑的過(guò)程可以概括為:03新知講解嘗試求解下圖中從A點(diǎn)到其余各點(diǎn)的最短路徑。探究實(shí)踐03新知講解嘗試求解下圖中從A點(diǎn)到其余各點(diǎn)的最短路徑。探究實(shí)踐目標(biāo)節(jié)點(diǎn)最短路徑總距離AA0BA→C→B8CA→C3DA→C→E→D13EA→C→E903新知講解三、迪杰斯特拉算法的程序?qū)崿F(xiàn)

人工推算最短路徑的方法效率低，易出錯(cuò)。通過(guò)計(jì)算機(jī)編程實(shí)現(xiàn)算法可以快速運(yùn)算出結(jié)果，極大地提高效率，解決更復(fù)雜的路徑查找問(wèn)題。03新知講解使用計(jì)算軟件尋找最短路徑。步驟1：將路線圖用數(shù)據(jù)表格表示。探究實(shí)踐03新知講解步驟2：將數(shù)據(jù)輸入計(jì)算機(jī)，計(jì)算最短路徑。探究實(shí)踐步驟3：在路線圖上驗(yàn)證答案。04課堂練習(xí)一、選擇題1、簡(jiǎn)化后的數(shù)據(jù)表格中，AB=12，BA=12，這是因?yàn)椋ǎ〢.路線是單向的B.路線是雙向的C.表格填寫(xiě)錯(cuò)誤D.需要對(duì)稱美觀2、迪杰斯特拉算法中，初始步驟需要將哪個(gè)點(diǎn)的相關(guān)路線放入橙框？（）A.終點(diǎn)B.起點(diǎn)C.中間點(diǎn)D.任意點(diǎn)3、在迪杰斯特拉算法中，橙框中的路線排序規(guī)則是（）A.從長(zhǎng)到短B.從短到長(zhǎng)C.隨機(jī)排序D.按字母順序BBB04課堂練習(xí)4、重新計(jì)算路徑長(zhǎng)度時(shí)，需要基于（）A.所有可能的路線B.已找到的最短路徑C.未探索的路線D.隨機(jī)選擇的路線5、迪杰斯特拉算法特別適合解決（）A.簡(jiǎn)單路線問(wèn)題B.復(fù)雜路線的最短路徑C.路線顏色標(biāo)記D.快遞包裹重量二、判斷題數(shù)據(jù)表格簡(jiǎn)化后，可以隨意刪除任意一半的數(shù)據(jù)。（）B×B04課堂練習(xí)三、操作題?路徑轉(zhuǎn)化?將下圖路線模型轉(zhuǎn)化為數(shù)據(jù)表格：A—B=5,A—C=2,B—D=8,C—D=4ABCDA052999B509998C299904D99984005拓展延伸常見(jiàn)最短路徑算法除了迪杰斯特拉算法之外，還有很多類似的最短路徑算法，如:弗洛伊德算法、貝爾曼-福特算法(Bellman-Ford)和SPFA算法等。這些算法各有特點(diǎn)，可滿足不同的需要。在現(xiàn)實(shí)生活中，最短路徑算法的應(yīng)用非常廣泛，比如手機(jī)導(dǎo)航、城市道路規(guī)劃和網(wǎng)絡(luò)通信等。05拓展延伸生活中的導(dǎo)航小助手手機(jī)地圖如何幫你找到最近的路？它其實(shí)用了類似迪杰斯特拉的算法，實(shí)時(shí)計(jì)算道路距離和擁堵情況，像一位隱形向?qū)湍阋?guī)劃最優(yōu)路線！05拓展延伸迷宮游戲的秘密路徑玩迷宮時(shí)如何快速找到出口？試試“貼墻法”或“最短步數(shù)法”，這和計(jì)算機(jī)尋找最短路徑的思路很像，都是通過(guò)不斷嘗試和排除錯(cuò)誤選項(xiàng)。出口入口05拓展延伸快遞小哥的智慧派送快遞公司如何安排送貨順序？他們用算法計(jì)算最短路線，減少時(shí)間和油耗，下次收到快遞時(shí)，可以想想背后的“數(shù)學(xué)魔法”哦！05拓展延伸算法背后的科學(xué)家故事迪杰斯特拉算法的發(fā)明者艾茲赫爾·戴克斯特拉（EdsgerDijkstra）是一位荷蘭計(jì)算機(jī)科學(xué)家，他最初設(shè)計(jì)這個(gè)算法是為了解決鐵路網(wǎng)絡(luò)的優(yōu)化問(wèn)題。06課堂總結(jié)1引入新知內(nèi)容最短路徑的算法2用數(shù)據(jù)表格表示路線圖3迪杰斯特拉算法4迪杰斯特拉算法的程序?qū)崿F(xiàn)5進(jìn)行相關(guān)知識(shí)拓展1234507板書(shū)設(shè)計(jì)最短路徑的算法1、進(jìn)行新知引入2、用數(shù)據(jù)表格表示路線圖3、迪杰斯特拉算法4、迪杰斯特拉算法的程序?qū)崿F(xiàn)5、進(jìn)行知識(shí)拓展課后作業(yè)。1、上網(wǎng)查找資料，了解用弗洛伊德算法(Floyd)求解最短路徑的基本過(guò)程。08課后作業(yè)1、如果兩點(diǎn)間用一個(gè)很大的數(shù)來(lái)表示路線長(zhǎng)度，說(shuō)明

。2、上網(wǎng)查找資料，了解用弗洛伊德算法(Floyd)求解最短路徑的基本過(guò)程。用弗洛伊德算法找最短路徑的過(guò)程，就像玩一個(gè)“找近路”的游戲，分三步走：（1）畫(huà)表