0. 前言
本文將介紹求解圖最短路徑的三個經(jīng)典算法：迪杰斯特拉 Dijkstra、弗洛伊德 Floyd卵佛、貝爾曼-福特 Bellman-Ford杨赤。
1. 迪杰斯特拉 Dijkstra
迪杰斯特拉算法，用于解決 “給定起始點到其余點的最短路徑” 問題级遭，即單源最短路徑算法望拖。時間復(fù)雜度為 。其本質(zhì)是貪心挫鸽。
算法步驟為：
- 用
G[n][n]二維數(shù)組記錄圖數(shù)據(jù)说敏；定義dis[n]一維數(shù)組記錄起始點到各點的最短路徑，初始化為INF（可以是 int 的最大值）丢郊；visited[n]一維數(shù)組記錄該點是否給訪問過（“訪問過”表示已找到最短路徑）盔沫，初始化為false。 - 選擇起始點
s枫匾，令dis[s] == 0架诞。 - 進行
n次循環(huán)：- 先從
dis[n]數(shù)組的所有未訪問結(jié)點中，找出最小值干茉，并記錄對應(yīng)下標p谴忧，令visited[p] = true。 - 更新
p所有鄰接點在dis[n]數(shù)組中的值角虫，更新規(guī)則為：dis[i] = min{dis[i], dis[p]+G[p][i]}
- 先從
示例及圖解：
核心偽代碼如下：
int dis[n];
bool visited[n];
for (int i = 0; i < n; i++) {
dis[i] = INF;
visited[i] = false;
}
dis[s] = 0;
for (int j = 0; j < n; j++) {
// 找 dis 數(shù)組中的最小值
int p = -1, min = INF;
for (int i = 0; i < n; i++) {
if (visited[i] == false && dis[i] < min) {
p = i;
min = dis[i];
}
}
visited[p] = true;
// 更新最小值所有鄰接點的值
for (int i = 0; i < n; i++) {
if (G[p][i] == INF || visited[i]) continue;
if (dis[i] > dis[p]+G[p][i]) {
dis[i] = dis[p] + G[p][i];
}
}
}
2. 弗洛伊德 Floyd
弗洛伊德是求解圖中任意兩點間最短路徑的算法沾谓。時間復(fù)雜度為 。其本質(zhì)是動態(tài)規(guī)劃戳鹅。
算法步驟為：
任意兩點間的最短距離用
d(x,y)表示均驶，初始值為兩點相連邊的權(quán)重。遍歷所有點 k枫虏，若任意兩點 i 和 j妇穴，滿足
d(i,j) > d(i,k) + d(k,j)爬虱，則d(i,j) = d(i,k) + d(k,j)。
代碼如下：
for (k = 1; k <= n; k++) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
算法分析：Floyd 的核心思想是動態(tài)規(guī)劃腾它。
我們先定義狀態(tài)：
d[k][i][j]跑筝，它表示經(jīng)過前 k 個節(jié)點，點 i 到點 j 的最短路徑携狭。-
d[k][i][j]可以由d[k-1][i][j]轉(zhuǎn)移而來：- 假設(shè)已經(jīng)求出继蜡，經(jīng)過前 k-1 個節(jié)點，任意兩點間的最短路徑逛腿。
- 那么，
d[k][i][j]就是 經(jīng)過前 k-1 個節(jié)點 i 到 j 最短路徑 與 經(jīng)過第 k 個節(jié)點 i 到 j 最短路徑 中的最小值仅颇。 - 而經(jīng)過第 k 個節(jié)點 i 到 j 最短路徑单默，就是 i 到 k 的最短路徑加上 k 到 j 的最短路徑。
- 最終忘瓦，得出狀態(tài)轉(zhuǎn)移方程為：
d[k][i][j] = min{d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]}搁廓。
由于
d[k][x][x]的狀態(tài)僅由d[k-1][x][x]轉(zhuǎn)移而來，所以我們可以進行優(yōu)化：d[i][j] = min{d[i][j], d[i][k] + d[k][j]}耕皮。
3. 貝爾曼-福特 Bellman-Ford
貝爾曼-福特算法境蜕，也是一個單源最短路徑算法，同時它還能處理負權(quán)邊凌停。算法時間復(fù)雜度為 粱年，
是點的個數(shù)，
是邊的個數(shù)罚拟。
算法步驟：
令源點為
s台诗，源點到任意點x的最短距離用d(x)表示。d(s)初始值為0赐俗，其余初始值為無窮拉队。進行
次松弛操作，松弛操作即：遍歷所有邊阻逮，對于每一條邊
e(i,j)粱快，如果存在d(j) > d(i) + e(i,j)，則令d(j) = d(i) + e(i,j)叔扼。
代碼如下：
for (i = 0; i < n-1; i++) {
for (j = 0; j < E; j++) {
if (d(e[j].to) > d(e[j].from) + e[j]) {
d(e[j].to) = d(e[j].from) + e[j];
}
}
}
算法分析：松弛操作的過程十分神奇事哭，直覺告訴我它肯定是正確的，但具體原因我也是一頭霧水币励。不過慷蠕，我們可以知道，每次松弛操作后食呻，至少能確定一個點的最短路徑流炕。所以澎现，需要進行 次。
Bellman-Ford 如何解決 Dijkstra 不能解決的負權(quán)邊問題呢每辟？如下圖剑辫，源點為 1 。若在 Dijkstra 中渠欺，第二次大循環(huán)時便會確定源點到點 3 的最短距離為 1 妹蔽；而在 Bellman-Ford 中，經(jīng)過松弛操作便可以確定源點到點 3 的最短距離為 -1 挠将。
Bellman-Ford 算法雖然能解決負權(quán)邊的問題胳岂，但時間復(fù)雜度還是偏高，當用于稠密圖時舔稀，是無法接受的乳丰。
因此，有人提出了 Bellman-Ford 的優(yōu)化算法：SPFA内贮。即第一次松弛操作产园，只需要對源點的鄰接邊進行即可；第二次松弛操作夜郁，只需要對與這些邊相連點的鄰接邊進行即可装悲；以此類推尤辱，直至所有邊遍歷完。這類似于 BSF 。
4. 參考
【原創(chuàng)】算法系列——四種最短路算法：Floyd护昧，Dijkstra滥玷，Bellman-Ford两疚，SPFA
