Aloha！嗨～我是少女人妻 Uerica ! 最近因為常常查演算法跟資料結構的文章，文章推薦跟 Youtube 影片首頁全都變成演算法跟資料結構了，害我不得不在晚上留點時間刷刷廢片啊 XDD！
路徑顧名思義就是在圖上取兩個點，分別做為起點和終點，可以規劃許多條起點到終點的路線，而不重複經過同一個點，就稱為路徑。而路徑的權重就是所經過的所有邊之權重和，邊的權重也可以是零或負數，畢竟圖只是一種儲存資料的結構。
最短路徑顧名思義就是起點到終點，權重最小的路徑，有可能很多條，也有可能不存在，但最短路徑不見得是邊最少、節點最少的路徑。
點對點最短路徑 Point-to-Point Shortest Path：
指定起點與終點，求出起點到終點的最短路徑。
單源最短路徑 Single Source Shortest Paths：
指定起點，求出起點到圖上每一點的最短路徑。
全點最短路徑 All Pairs Shortest Paths：
不特別指定起點與終點，而是求出圖上所有兩點之間的最短路徑。
重要概念
戴克斯特拉演算法是最早求最短路徑的演算法，屬於單源最短路徑演算法，也就是一個點到其他所有點的最短路徑為何，不過要注意，此演算法邊的權重不可是負數。此演算法首先會創一個只有起點的集合，接著開始逐一找出最短路徑，而將最短路徑會抵達的節點列入集合中，重複操作直到所有點都在集合內為止。
Dijkstra Algorithm 圖解
好的～灰姑娘終於跑累了，而且玻璃鞋實在不好跑啊，於是決定之後都要開車出門不跑了！不過灰姑娘每次開車都要被收過路費，每一條路的過路費又不同，完全看當地的物價來決定，省吃儉用的灰姑娘決定好好來計算一番每個點最便宜的路線為何！省下的錢可以再買幾雙玻璃鞋吧！
首先灰姑娘先畫了這張圖，為了記錄從家裡到各點之間的價格，在不曉得能不能到達前都是無窮遠，所以先將所有價格都設為無窮大，之後有比較小的數字再更新上去。
然後打開王子給的所有路徑價格的地圖
首先從家裡 Home 出發，有兩條路是 Home -> Bank 跟 Home -> Store
兩條路徑分別是 $150 跟 $50 ，灰姑娘記性不好所以先寫下來。
從兩條路線中選最便宜的一條路徑 Home -> Store 畫起來，確定這條路線是最佳路徑，並從此路徑做延伸。
於是再找出從 Store 可以延伸至其他點的所有路徑，此時發現 Home -> Store -> Bank 是 $120 ( $50 + $70 ) ，比原本 Home -> Bank 的 $150 還便宜！而 Home -> Store -> Shop 是 $130 ( $50 + $80 ) ， Home -> Store -> Castle 是 $110 ( $50 + $60 ) ，
再把價格都記起來，有比較便宜就更新上去！
再選擇當中最便宜的一條路，於是連接到 Castle
再從 Castle 延伸出所有可到達其他點的路徑，不過 Castle -> Shop 比較貴，要 $160 ($50 + $60 + $50) ，所以不用更新原本的價格
再選擇一條最便宜的路徑，去 Shop 這條沒有比較便宜，直接撇除！
再選擇下一條比較便宜的路，連接到了 Bank
將 Bank 可延伸的所有路徑標示起來，此時多一條到 Bar 的路徑
因 Home -> Store -> Bank -> Bar 的價格是 $230，比無窮大還小，所以更新原本的資料
再選擇下一條較便宜的路，連接到 Shop
再下一條，連接到 Bar
其他比較貴的通通撇除
好的！這就是最便宜的路線以及家裡到各點的價格啦～善良的灰姑娘還把資料分給了兩個姊姊跟繼母呢！
Dijkstra Algorithm 時間複雜度
因戴克斯特拉演算法會使用相鄰矩陣 Adjacency Matrix 的方式來執行，所以時間複雜度是 O(n^2)，若用斐波那契堆積 Fibonacci heap 可降到 O(e + log n log) 其中的 e 是指有幾個邊
參考資料：
好的今天就到這邊啦！感謝閱讀，明天見啦掰掰！
iThome鐵人賽
看影片追技術