擁抱「資料結構」的「演算法」(29) - 戴克斯特拉演算法求最短路徑

 

前言

對圖形的搜尋有了基本觀念之後，接下來要在圖形的邊加入權重的部分，這樣就能找到最短路徑

生活常識

你有自己規劃行程的經驗嗎？如果朋友住在台中住在想去花蓮旅遊，那麼你會怎麼建議行程呢？是建議從南投走橫貫公路，還是從繞到台北宜蘭，還是打開 googe map 直接看哪個路徑比較短，或是花費的時間比較少，由下圖可以看到 google map 推薦路程時間最少的(走往台北的路徑)，而不是距離最短的路徑(走往南投的路徑)



專業知識 - 戴克斯特拉演算法 Dijkstra's algorithm

戴克斯特拉演算法因為音譯的關係有蠻多種說法的，每一種名字都蠻常的XD，我自己是比較習慣用英文記憶XD，回歸正題，如果僅以邊作為挑選路徑的考量，也就是圖形中 A 點到 B 點經過幾個邊，可以使用昨天介紹的廣度或深度演算法，但如果加上時間的考量，則廣度搜尋演算法的結果並不一定會等於戴克斯特拉演算法的結果

如下圖，起點為 A 點，目的地為 E 點：

  • 左圖
    沒有時間的權重，所以最短路徑會選 ACE，此路段最少，因為只需要經過2個邊

  • 右圖
    加上時間的權重，單位為分鐘，ACE 花費時間為 13(9+4) 分鐘，雖然 ABDE 要走 3 個邊但只需要花 10 分鐘，所以走 ABDE 最快



最短路徑 Single-Pair Shortest Path

有一個有向加權圖形 G = ( V, E )，最短路徑為圖中兩頂點間的最短路徑，也就是權重加總數值最小者，其中加權的部分，就看個人的考量，也許是時間，或是開車油錢等等

例子

以下圖為例，權重為公里，想要找到 A 到任一點最短的路徑，透過戴克斯特拉演算法要如何取得結果，這邊要特別注意，使用戴克斯特拉演算法時，圖形中的權重不能有負數(正負數)，否則演算法的結果可能會有錯誤，須改用其他演算法，像是貝爾曼福特演算法(Bellman-Ford algorithm)

先來看搜尋結果，稍後會有詳細的步驟說明



可由步驟 5 觀察到，A 到任一點的最短距離
A 到 A 的最短距離為 0
A 到 B 的最短距離為 1
A 到 C 的最短距離為 4
A 到 D 的最短距離為 6
A 到 E 的最短距離為 6

步驟說明：

  1. 尋找與 A 到相鄰的點 B 與 C 的最短路徑
    A 到 B 點：1 公里
    A 到 C 點：5 公里
    此時不知道 D 與 E 距離 A 多遠，所以先畫 - 符號表示無窮大

  2. 尋找與 B 到相鄰的點 C 與 D 的最短路徑
    A 到 C 點：上個步驟的 A 到 C 是 5 公里，但 A 經過 B 在到 C 的距離更短，只需要 4 公里，所以將 A 到 C 的距離更新為 4
    A 到 D 點：A 到 D 點的距離為 6 = 1( A 到 B ) + 5( B 到 D)，將表格中的 - 符號更新為 6

  3. 尋找與 C 到相鄰的點 E 的最短路徑
    A 到 E 點：先查詢表格，A 到 C 的最短距離計算的結果為 4 公里( A 到 B 再到 C)，C 到 E 的距離為 2 公里，所以 A 到 E 的最短距離為 6 ( 2 + 4 ) 公里

  4. 尋找與 D 到相鄰的點 E 的最短路徑
    A 到 E 點：先查詢表格，A 到 D 的最短距離為 6 公里，D 到 E 為 4 公里，所以 A 經過 D 再到 E 的路徑為 10 ( 6 + 4 ) 公里，但與第 3 步驟的 A 到 E 中間通過 C 點比較，發現 10 大於 6 ，所以 10 不是最短路徑，不更新表格數值

  5. 尋找與 D 到相鄰的點 E 的最短路徑
    E 點沒有相鄰頂點，結束搜尋，如果表格中還含有 - 符號，代表 A 到無法抵達此點

今日小結

執行戴克斯特拉演算法，在計算過程中，我們需要去取得資料並記錄結果，這個過程需要到記憶體空間，也就是如何將這些資料儲存起來，會使用到之前提到的資料結構，你會選擇那些資料結構來搭配這個演算法呢？其實之前的章節都有說過，不訪動動腦想想看哦

今日謎題

小美要從丹麥(Danmark)到澳洲(Austria)找一個人，下圖是任意門的傳送點與路徑，上面是標注每條路線要走幾公里才能抵達下一個任意門，你可以幫小美找出最短路徑嗎？這條最短路徑似乎按藏著關於小美要找的人的訊息，你能發現嗎？



昨日謎題

謎題說明：利用走梯子遊戲來感受一下深度優先搜尋，走訪三條路徑之後，可以發現只有第一條可以組成一個有意義的單字，答案就是 DEPTH(深度)，你答對了嗎



留言

張貼留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

以下是自己的 CPE 一顆星選集 解題紀錄 (共有 49 題) 每次考試都會從一顆星選集中抽 1 提出來考 算是比較能把握的部分，重點筆記整理如下 內容包含題目說明、程式碼、註解說明、解答、考古題統計(下方土黃色日期) 解題使用的程式語言是  JAVA  目前有提供 10 題的試閱 另有提供完整 49 題的完整解答 ( pdf 檔 )， 共 305 頁， 售價 $399 元 ， 若有需要請來信購買 greens2314@gmail.com 推薦閱讀： 建議熟讀 java 基本觀念，與使用 eclipse 練習， 等熟悉之後再到瘋狂程設考試(一定要懂如何查 JAVA API 與使用英漢字典) Java 考試常用的方法或類別 Eclipse 常用小技巧 CPE 一顆星選集： 編號 | 題目名稱 | 歷屆考古題日期 1. Vito's family (CPE10406, UVA10041) 2024/04/23 可與第 40 題一起看 2. Hashmat the brave warrior (CPE10407, UVA10055) 3. Primary Arithmetic (CPE10404, UVA10035) 　 2011/05/25、2023/03/21 4. The 3n + 1 problem (CPE10400, UVA100) 　 2010/06/09 5. You can say 11 (CPE10460, UVA10929) 　 2011/12/20 6. Bangla Numbers (CPE10414, UVA10101) 　 2018/12/18 7. List of Conquests (CPE21924, UVA10420) 　 2019/03/26 　　可與 第 8, 11, 43 題一起看 字元與字串 8. What's Cryptanalysis? (CPE10402, UVA10008) 　　可與 第 7, 11, 43 題一起看 9. Decode the Mad man (CPE10425, UVA10222) 　 2021/10/19 10. Problem J: Summing Digits (CPE10473, UVA11332) ...
Read more »

Visual Studio 自動排版格式化程式碼

圖片
在團隊開發過程中，什麼時候是程式碼瘋狂修改的階段呢， 無非就是Code Review了，有時候卡個幾天或是幾個月都是有可能的， 裡面常出現的comment，每次幾乎都會出現的就是排版的問題， 例如空白多一個少一個，括號還沒換行等等的小瑕疵， 對於心思不夠細膩的人而言，真的十分的惱人 團隊中喜歡將大括號換行， 例如： if(true) {   //code } else {   //code } 那也許有些團隊喜歡： if(true){   //code }else{   //code } 有時候不只括號要不要換行，連else要不要換行都有各自的喜好， 所以有時候要統一使用團隊規定的喜好真的會有眼殘的時候， 自己檢查老半天可能還是有漏網之魚， 但現在不用擔心啦！ 只要使用Format 格式化文件就能為你分憂解勞， 設定方式如下： 編輯 > 進階 > 格式化文件 Visual Studio會根據你的環境設定幫你自動重新排版 設定方式如下： 工具 > 選項 切換到 文字編輯器 > C# >程式碼樣式 > 格式化 > 新行 這邊可以設定很多換行的邏輯， 將對應的項目打勾跟取消勾選，下面的黑色區域會顯示排版的格式， 可根據自己或是團隊的喜好去做調整，即可自動排出你想要的格式囉！ 如果覺得 編輯 > 進階 > 格式化文件 這個選項太難找到， 可以參考這篇文章，將他加入在明顯的工具列區域喔 http://greens2314.blogspot.tw/2017/09/visual-studio-2015.html
Read more »

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明

圖片
    👉   CPE 一顆星選集列表(49題) 題目說明與解答 題目 Vito 在紐約有非常多的親戚，他希望在紐約找到一間房子，這間房子到每個親戚家的距離總和，要是最少的距離 輸入說明 輸入資料包含很多筆測試資料 每筆測資，包含親戚數量與每位親戚家的街號 親戚數量介於1~499、街道範圍介於1~29999 多位親戚可住在同一條街 輸出說明 針對每筆測試資料，計算出 Vito 到每位親戚家的最短距離總和 街與街的距離 = 街道數字相減取絕對值 解題技巧 中位數 是指一組數字的中間數字；即是有一半數字的值大於中位數，而另一半數字的值小於中位數，其意義是在所有資料中居於中間位置的代表 排序 街道的數字同時代表距離，透過排序，可得知中位數 解題過程 取得輸入 取得資料筆數 根據資料筆數取得親戚數量 根據親戚數量取得街道編號 將街道編號存入陣列中 將親戚的街道位置 由小至大 排序 呼叫 Arrays 類別提供的 sort() 方法 https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html 假設親戚有 5 位，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街 計算中位數 中位數在陣列中的索引 = 親戚數量 / 2 假設親戚有 5 位( 奇數) ，分別住在：2、5、8、4、2街 排序後為：2 、2、4、5、8街，其中 4 為中位數，中位數有 1 個 5位親戚 / 2 = 2.5，取整數，陣列索引 2 的位置，儲存的是第 4 街 假設親戚有 4位 (偶數) ，分別住在：2、5、8、4街 排序後為：2 、4、5、8街，其中 4 或 5 為中位數， 中位數有 2 個，擇一即可 4位親戚 / 2 = 2，陣列索引 2 的位置，儲存的是 5 街 計算最小距離總和並印出 宣告 sum 變數，統計距離 使用 foreach 將各街道編號 減掉 中位數編號，取絕對值並進行家總 取絕對值要呼叫  Math.abs ()  方法 奇數情況 ： 中位數有 1 個 假設親戚有 5 位   ，分別住在： 2 、2、 4 、5、8 街 中位數 4 ，Vito 住在 4 街，到其他親戚家的距離總和即是最小值 9   偶數情況 ： ...
Read more »