Dijkstra算法與Prim算法的異同案例詳解
Dijkstra簡(jiǎn)述
Dijkstra算法用于構(gòu)建單源點(diǎn)的最短路徑樹(shù)(MST)——即樹(shù)中某個(gè)點(diǎn)到任何其他點(diǎn)的距離都是最短的。例如,構(gòu)建地圖應(yīng)用時(shí)查找自己的坐標(biāo)離某個(gè)地標(biāo)的最短距離??梢杂糜谟邢驁D,但是不能存在負(fù)權(quán)值(Bellman-Ford可以處理負(fù)權(quán)值)。
- 偽代碼
Dijkstra() { for each u in G,V { //此處做初始化操作,給每個(gè)節(jié)點(diǎn)u賦鍵值+∞,設(shè)置空為父節(jié)點(diǎn) u.key = +∞ u.parent = NULL } //選初始點(diǎn)r,Q是無(wú)向圖G中所有點(diǎn)V的權(quán)值優(yōu)先隊(duì)列,key可看作源點(diǎn)到u的距離 r.key = 0 Q = G,V while(Q != ∅) { //取出Q中權(quán)值最小值的點(diǎn)u u = extractMin(Q) //取點(diǎn)u連接的所有節(jié)點(diǎn)(即無(wú)向圖G的鄰接表中的第u個(gè)鏈表) for each v ∈ G.Adj[u] { if (v ∈ Q) and (w(u, v) < key) { //若該節(jié)點(diǎn)仍在Q中且權(quán)值w(w,v)小于其原始權(quán)值,則進(jìn)行松弛操作! v.parent = u v.key = w(u, v) + u.key } } } }
Prim簡(jiǎn)述
Prim算法用于構(gòu)建最小生成樹(shù)——即樹(shù)中所有邊的權(quán)值之和最小。例如,構(gòu)建電路板,使所有邊的和花費(fèi)最少。只能用于無(wú)向圖。
- 偽代碼
//無(wú)向圖G, 權(quán)值w, 起始點(diǎn)r MST(G, w, r) { for each u in G,V { //此處做初始化操作,給每個(gè)節(jié)點(diǎn)u賦鍵值+∞,設(shè)置空為父節(jié)點(diǎn) u.key = +∞ u.parent = NULL } //選初始點(diǎn)r,Q是無(wú)向圖G中所有點(diǎn)V的權(quán)值優(yōu)先隊(duì)列,key可看作u到下一個(gè)節(jié)點(diǎn)v的距離 r.key = 0 Q = G,V while(Q != ∅) { //取出Q中權(quán)值最小值的點(diǎn)u u = extractMin(Q) //取點(diǎn)u連接的所有節(jié)點(diǎn)(即無(wú)向圖G的鄰接表中的第u個(gè)鏈表) for each v ∈ G.Adj[u] { if (v ∈ Q) and (w(u, v) < key) { //若該節(jié)點(diǎn)仍在Q中且權(quán)值w(w,v)小于其原始權(quán)值,則進(jìn)行松弛操作! v.parent = u v.key = w(u, v) } } } }
異
MST中任意AB兩點(diǎn)之間的距離,并不比原始圖中AB的距離短,即原始圖中可能存在邊E(A,B)**小于**MST中的E(A,B)。
注意上述兩個(gè)偽算法的差別只在于最后循環(huán)體內(nèi)的松弛操作。
- 最小生成樹(shù)只關(guān)心所有邊的和最小,所以有v.key = w(u, v),即每個(gè)點(diǎn)直連其他點(diǎn)的最小值(最多只有兩個(gè)節(jié)點(diǎn)之間的權(quán)值和)
- 最短路徑樹(shù)只搜索權(quán)值最小,所以有v.key = w(u, v) + u.key,即每個(gè)點(diǎn)到其他點(diǎn)的最小值(最少是兩個(gè)節(jié)之間的權(quán)值和)
簡(jiǎn)單總結(jié)就是,Dijkstra的松弛操作加上了到起點(diǎn)的距離,而Prim只有相鄰節(jié)點(diǎn)的權(quán)值。
同
思想
都是使用貪婪和線性規(guī)劃,每一步都是選擇權(quán)值/花費(fèi)最小的邊。
貪婪:一個(gè)局部最有解也是全局最優(yōu)解;
線性規(guī)劃:主問(wèn)題包含n個(gè)子問(wèn)題,而且其中有重疊的子問(wèn)題。
Dijkstra算法通過(guò)線性規(guī)劃緩存了最優(yōu)子路徑的解,每一步也通過(guò)貪婪算法來(lái)選擇最小的邊。
Prim算法通過(guò)貪婪來(lái)選擇最小的邊,而Prim的每個(gè)子樹(shù)都是最小生成樹(shù)說(shuō)明滿足線性規(guī)劃的兩個(gè)條件。
時(shí)間復(fù)雜度
Time = θ( V * T1 + E * T2)
其中T1為取出鍵值最小點(diǎn)的時(shí)間,T2為降低鍵值的時(shí)間,取決于數(shù)據(jù)結(jié)構(gòu)。
- 數(shù)組
T1= O(V), T2 = O(1), TIME = O(V * V + E) = O(V * V) - 二叉堆
T1 = O(lgV), T2 = O(lgV), TIME = O(V * lgV + E * lgV) - 斐波那契堆
T1 = O(lgV), T2 = O(1), TIME = O(V * lgV + E) = O(V * lgV)
對(duì)于稀疏圖來(lái)說(shuō),E遠(yuǎn)小于V*V,所以二叉堆比較好;
而對(duì)于密集圖來(lái)說(shuō),E=V*V,所以數(shù)組比較好;
斐波那契堆是最好的情況。
Dijkstra特例
當(dāng)邊的權(quán)值都為1的時(shí)候,可以用DFS(廣度優(yōu)先搜索)優(yōu)化時(shí)間復(fù)雜度。
- 使用FIFO(先進(jìn)先出)隊(duì)列代替優(yōu)先隊(duì)列,優(yōu)化了降低鍵值T2的操作為O(1)
- 松弛操作改為
if d[v] = +∞ { d[v] = d[u] + 1 enqueue(Q, v) }
優(yōu)化了取出鍵值最小點(diǎn)的時(shí)間T1 = O(1)
總的時(shí)間復(fù)雜度
TIME = V + E
到此這篇關(guān)于Dijkstra算法與Prim算法的異同案例詳解的文章就介紹到這了,更多相關(guān)Dijkstra算法與Prim算法的異同內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)Dijkstra算法的示例代碼
迪杰斯特拉算法(Dijkstra)是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法。本文將用C++實(shí)現(xiàn)Dijkstra算法,需要的可以參考一下2022-07-07C語(yǔ)言代碼實(shí)現(xiàn)猜數(shù)字
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言代碼實(shí)現(xiàn)猜數(shù)字,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-11-11簡(jiǎn)單分析針對(duì)ARM平臺(tái)的C語(yǔ)言程序的編譯問(wèn)題
這篇文章主要介紹了針對(duì)ARM平臺(tái)的C語(yǔ)言程序的編譯問(wèn)題,從優(yōu)化編譯選項(xiàng)的幾個(gè)方面進(jìn)行分析,需要的朋友可以參考下2015-12-12