前言
Dijkstra算法是應(yīng)用于圖中單源最短路徑的搜索拢肆。我在這記錄下我在學(xué)習(xí)該算法時的一些想法援制、理解與總結(jié)迄本。首先我會寫一段預(yù)備知識爷辙，以便于之后的理解。
算法基礎(chǔ)
- 選擇點(diǎn)到其他點(diǎn)的最短距離
- 局部最優(yōu)是全局最優(yōu)的充分必要條件
基礎(chǔ)1：
在一張權(quán)值都是 同號 的圖中竹椒，假設(shè)存在：①點(diǎn)A童太；②與A點(diǎn)相連的最短弧的弧頭C；那么路徑(A,C)為點(diǎn)A到點(diǎn)C的最短路徑胸完。
如圖所示书释，(A,C) 是點(diǎn)A到點(diǎn)C的最短路徑。
解釋：在權(quán)值都為正的情況下赊窥，沒走一個點(diǎn)爆惧，其路徑只會增加。所以與點(diǎn)A相接最短的弧是抵達(dá)弧頭的最短路徑锨能。
正文
集合{S}：用來存放已尋找到最短路徑的點(diǎn)扯再。
集合{V}：全集
集合{V - S} 剩下的未找到最短路徑的點(diǎn)集
如果集合{S}包括了所有的點(diǎn)，那么圖的單源最短路徑尋找結(jié)束址遇。
算法開始的時候集合{S}中只包括原點(diǎn)熄阻，Dijkstra算法的過程是逐漸填充集合{S}的過程。
怎么填充倔约？
在集合{V - S}中找一個距離{S}最近的點(diǎn)秃殉，命其為 點(diǎn)V 將其加入集合{S}中。
解釋如圖：
注意：
①這張圖和前面那張圖沒有任何聯(lián)系；
②圖中的虛線并不是真實(shí)存在的線复濒，虛線上的數(shù)組不是點(diǎn)至原點(diǎn)的路徑長度脖卖，而是集合{S}到點(diǎn)的路徑長度乒省，這些數(shù)值的需要計(jì)算巧颈；
在填充的過程中，會發(fā)現(xiàn)一個問題袖扛。每添加一個點(diǎn)之后砸泛，集合{S} 至集合{V - S}中點(diǎn)的最短距離可能會發(fā)生變化。
例如 圖2 ：添加點(diǎn)C之后蛆封，集合{S}到點(diǎn)B的最短距離變?yōu)橄冉?jīng)過點(diǎn)C唇礁，在到達(dá)點(diǎn)B。即 5+4 < 10惨篱。因此再每加入一個點(diǎn)后就要時刻更新集合{S} 至 集合{V - S}中點(diǎn)的最短距離盏筐。
總結(jié)：Dijkstra算法一共需要三步
- ① 創(chuàng)建集合{S}，將原點(diǎn)加入集合{S}砸讳。計(jì)算集合{S}到各點(diǎn)的距離琢融，并儲存。
- ② 尋找目前距離集合{S}最短距離的 點(diǎn)V 簿寂，將 點(diǎn)V 加入集合{S}
- ③ 更新集合{V - S} 中的點(diǎn)距離 集合{S} 的距離
應(yīng)用
#define MAX_SIZE 100
int route[MAX_SIZE][MAX_SIZE];//路徑
int curDis[MAX_SIZE];//當(dāng)前最短路徑
int pre[MAX_SIZE];//前驅(qū)
bool Set[MAX_SIZE];//集合{S}
int N;//結(jié)點(diǎn)個數(shù)
void shortestPath(const int start, const int dest)
{
//初始化
fill(Set, Set+N, false);
fill(curDis, curDis+N, INF);
int i;
for(i = 0 ; i < N ; i++) pre[i] = i;
curDis[start] = 0;
//遍歷除原點(diǎn)外的頂點(diǎn)漾抬，因?yàn)槊看窝h(huán)都會尋找到一個可以加入集合{S}中的點(diǎn)，
for(i = 0 ; i < N ; i++){
//尋找 {V-S} 到原點(diǎn)最短路徑的點(diǎn)
int v = -1, MIN = INF;
for(int j = 0 ; j < N ; j++){
if(!Set[j] && curDis[j] < MIN)
v = j;
min = curDis[j];
}
}
if(v == -1) break;//有些結(jié)點(diǎn)無法到達(dá)
Set[v] = true;
//更新 {V-S} 中的最短路徑
for(int j = 0 ; j < N ; j++){
if(!Set[j] && route[u][j] != INF){
if(curDis[v] + route[v][j] < curDis[j]){
curDis[j] = curDis[v] + route[v][j];
pre[j] = u;//設(shè)置前驅(qū)
}else if(distance == shortestDistance[iY]){
//這里處理第二選擇情況
}
}
}
}
}
注意：權(quán)值必須是全是正的常遂，或者全是負(fù)的纳令。兩種情況的結(jié)果會不同，我只做在權(quán)值全為正的情況克胳。如果想求最大路徑平绩，可以將正權(quán)值都制負(fù)，然后使用Dijkstra算法尋找最小值漠另。然后再去絕對值捏雌，則是最大路徑。
