iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 16
0
自我挑戰組

學習筆記系列 第 21

Floyd-Warshall 、Dijkstra Algorithm 筆記

記錄學習內容。看網路上大大們的文章和影片,做些紀錄。
以下內容大多來自網路上大大們的文章。截圖也來自文章和影片。
還不了解,內容可能有錯誤。

圖有很多 最短路徑的演算法 。

從某個點 到 其他全部點的 最短路徑 。
或是 某個點 到 終點的 最短路徑
之類的問題。

每個邊 都有 1 個變數 : weight, 代表這條路的距離 。

這類問題就是 找到 一些邊 (路) ,這些邊相加起來的weight要是最小值(代表最短路徑)

先從Floyd-Warshall開始看
All Pairs Shortest Path (Floyd-Warshall) - Dynamic Programming

筆記:
Floyd-Warshall演算法

Floyd-Warshall中文亦稱 弗洛伊德演算法

可以正確處理有向圖或負權(但不可存在負權迴路)的最短路徑問題

什麼是負權迴路(Negative Cycles)?

Floyd Warshall All Pairs Shortest Path Algorithm | Graph Theory | Dynamic Programming
https://ithelp.ithome.com.tw/upload/images/20200916/20111994ZM9OiuLs4K.png

1、3、2所圍成的圈圈 ,就叫做負權迴路(Negative Cycles) 。
今天要1到 1 的話 ,原本是0
,但是現在 可以 1 --> 3 -- >2 -- >1 = -1
所以判斷負權迴路(Negative Cycles)的方法就是:自己到自己變成負數
https://ithelp.ithome.com.tw/upload/images/20200916/20111994bpW7lUhXHt.png

複雜度

https://ithelp.ithome.com.tw/upload/images/20200916/20111994XQHxAAQTeN.png

> Floyd-Warshall演算法的原理是動態規劃

因為是迴圈 加上 陣列(存檔空間)

接著來看:
3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method
[演算法] 最短路徑 (Dijkstra 演算法)

Dijkstra Algorithm。主要內容是指定一個點 (源點) 到其餘各個頂點的最短路徑,也稱作「單源最短路徑」。

Dijkstra Algorithm 在邊長是 負數 的情況下,答案可能會是錯誤的。

像是現在從1出發 , 會先選 1 到 2邊長。
接著選 1 到 4 邊長。
接著選 4 到 3邊長 。
這時後就會發現 1 到 4 到 3 到2的距離是 -3 。
但是 用Dijkstra Algorithm 的方式 ,1 到 2 的最短距離是 3,所以答案錯誤
https://ithelp.ithome.com.tw/upload/images/20200916/20111994FkmGGFiEIP.png

看一下維基的時間複雜度:
戴克斯特拉演算法
目前學的是第一種 。 其餘的都不會:
https://ithelp.ithome.com.tw/upload/images/20200916/20111994pCfp8sEj1k.png

接著來看離散數學教學的Dijkstra Algorithm:
[Discrete Mathematics] Dijkstra's Algorithm
https://ithelp.ithome.com.tw/upload/images/20200916/20111994xdc2CX469q.png
Dijkstra's Algorithm (戴克斯特拉演算法)
這個演算法 ,代表 某個點(a) 到 所有其他點(除了a以外) 的 最短路徑 。

一開始 先從 a點 開始檢查 ,與a相鄰的 就寫 數字長度 ,
與a不相鄰,代表走不到,所以寫無窮遠 。

a檢查完(觀察完)所有點後,看哪個點與a最近,發現g最近
,就代表走a -- > g 這條路 。

下一輪 再從 g開始檢查 。像是圖中 g到b 是13 ,發現比原本14還少。
所以從(a,14)改成(g,13) 。

g檢查完所有的點後 ,發現 b最近 。
路徑就變成a -- > g -- > b

接著就是 b檢查
,b檢查完所有點後 ,發現i最近
路徑變成a -- > g -- > b -- > i

這邊發現這樣寫很奇怪 。因為b走不到i ,

所以這個演算法 ,不是一個點接著一個點走的。
而是 一個點檢查、檢查完後,選擇目前最短的點 ,再繼續最短的點檢查…
直到所有點都跑完。

最後的結果 會顯示 a 到 所有其他點 的 最小長度 。
然後會形成一個樹 ,這個樹叫做Minimum Spanning Tree(MST,最小生成樹)

MST,最小生成樹 :

在一個圖中如果選了全部的點,而這全部的點又相連 ,然後是一個樹,就叫做Spanning Tree,
這些Spanning Tree 中,有些樹weight總和是最小的 ,這些樹就是Minimum Spanning Tree

關於Minimum Spanning Tree最小生成數:
Minimum Spanning Tree:Intro(簡介)

Dijkstra's Algorithm (戴克斯特拉演算法)
這個演算法 ,代表 某個點(a) 到 所有其他點(除了a以外) 的 最短路徑 。
所以 好像不一定是Minimum Spanning Tree(MST,最小生成樹)
不一定 會 是 weight總和是最小的


上一篇
NP, NP-Complete, NP-Hard問題
下一篇
Python ,OpenCV 練習
系列文
學習筆記46

尚未有邦友留言

立即登入留言