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)的最短距離。可以用于有向圖，但是不能存在負(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