系列文章目錄單源最短路徑（1）：Dijkstra算法
單源最短路徑（2）：Bellman_Ford算法
單源最短路徑（3）：SPFA算法
單源最短路徑（4）：總結(jié)
Dijkstra算法（中文名：迪杰斯特拉算法）是由荷蘭計(jì)算機(jī)科學(xué)家Edsger Wybe Dijkstra提出。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。舉例來(lái)說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示城市間開車行經(jīng)的距離，該算法可以用來(lái)找到兩個(gè)城市之間的最短路徑。
我們用一個(gè)例子來(lái)具體說明迪杰斯特拉算法的流程。
定義源點(diǎn)為0，dist[i]為源點(diǎn)0到頂點(diǎn)i的最短路徑。其過程描述如下：
| 步驟 | dist[1] | dist[2] | dist[3] | dist[4] | 已找到的集合 |
|---|---|---|---|---|---|
| 第1步 | 8 | 1 | 2 | +∞ | { 2 } |
| 第2步 | 8 | × | 2 | 4 | { 2, 3 } |
| 第3步 | 5 | × | × | 4 | { 2, 3, 4 } |
| 第4步 | 5 | × | × | × | { 2, 3, 4, 1 } |
| 第5步 | × | × | × | × | { 2, 3, 4, 1 } |
第1步：從源點(diǎn)0開始，找到與其鄰接的點(diǎn)：1，2，3，更新dist[]數(shù)組，因0不與4鄰接，故dist[4]為正無(wú)窮。在dist[]中找到最小值，其頂點(diǎn)為2，即此時(shí)已找到0到2的最短路。
第2步：從2開始，繼續(xù)更新dist[]數(shù)組：2與1不鄰接，不更新；2與3鄰接，因0→2→3比dist[3]大，故不更新dist[3] ；2與4鄰接，因0→2→4比dist[4]小，故更新dist[4]為4。在dist[]中找到最小值，其頂點(diǎn)為3，即此時(shí)又找到0到3的最短路。
第3步：從3開始，繼續(xù)更新dist[]數(shù)組：3與1鄰接，因0→3→1比dist[1]小，更新dist[1]為5；3與4鄰接，因0→3→4比dist[4]大，故不更新。在dist[]中找到最小值，其頂點(diǎn)為4，即此時(shí)又找到0到4的最短路。
第4步：從4開始，繼續(xù)更新dist[]數(shù)組：4與1不鄰接，不更新。在dist[]中找到最小值，其頂點(diǎn)為1，即此時(shí)又找到0到1的最短路。
第5步：所有點(diǎn)都已找到，停止。
對(duì)于上述步驟，你可能存在以下的疑問：
若A作為源點(diǎn)，與其鄰接的只有B，C，D三點(diǎn)，其dist[]最小時(shí)頂點(diǎn)為C，即就可以確定A→C為A到C的最短路。但是我們存在疑問的是：是否還存在另一條路徑使A到C的距離更??？ 用反證法證明。
假設(shè)存在如上圖的紅色虛線路徑，使A→D→C的距離更小，那么A→D作為A→D→C的子路徑，其距離也比A→C小，這與前面所述“dist[]最小時(shí)頂點(diǎn)為C”矛盾，故假設(shè)不成立。因此這個(gè)疑問不存在。
根據(jù)上面的證明，我們可以推斷出，Dijkstra每次循環(huán)都可以確定一個(gè)頂點(diǎn)的最短路徑，故程序需要循環(huán)n-1次。
using namespace std;int matrix[100][100]; // 鄰接矩陣bool visited[100]; // 標(biāo)記數(shù)組int dist[100]; // 源點(diǎn)到頂點(diǎn)i的最短距離int path[100]; // 記錄最短路的路徑int source; // 源點(diǎn)int vertex_num; // 頂點(diǎn)數(shù)int edge_num; // 邊數(shù)void Dijkstra(int source){ memset(visited, 0, sizeof(visited)); // 初始化標(biāo)記數(shù)組 visited[source] = true; for (int i = 0; i < vertex_num;="" i++)="" {="" dist[i]="matrix[source][i];" path[i]="source;" }="">int min_cost; // 權(quán)值最小 int min_cost_index; // 權(quán)值最小的下標(biāo) for (int i = 1; i < vertex_num;="" i++)="">// 找到源點(diǎn)到另外 vertex_num-1 個(gè)點(diǎn)的最短路徑 { min_cost = INT_MAX; for (int j = 0; j < vertex_num;="" j++)="" {="">if (visited[j] == false && dist[j] < min_cost)="">// 找到權(quán)值最小 { min_cost = dist[j]; min_cost_index = j; } } visited[min_cost_index] = true; // 該點(diǎn)已找到，進(jìn)行標(biāo)記 for (int j = 0; j < vertex_num;="" j++)="">// 更新 dist 數(shù)組 { if (visited[j] == false && matrix[min_cost_index][j] != INT_MAX && // 確保兩點(diǎn)之間有邊 matrix[min_cost_index][j] + min_cost < dist[j])="" {="" dist[j]="matrix[min_cost_index][j]" +="" min_cost;="" path[j]="min_cost_index;" }="" }="">int main(){ cout <>'請(qǐng)輸入圖的頂點(diǎn)數(shù)（<>; cin >> vertex_num; cout <>'請(qǐng)輸入圖的邊數(shù)：'; cin >> edge_num; for (int i = 0; i < vertex_num;="" i++)="">for (int j = 0; j < vertex_num;="" j++)="" matrix[i][j]="(i" !="j)" int_max="" :="">0; // 初始化 matrix 數(shù)組 cout <>'請(qǐng)輸入邊的信息：\n'; int u, v, w; for (int i = 0; i < edge_num;="" i++)="" {="">cin >> u >> v >> w; matrix[u][v] = matrix[v][u] = w; } cout <>'請(qǐng)輸入源點(diǎn)（<> < vertex_num=""><>'）：'; cin >> source; Dijkstra(source); for (int i = 0; i < vertex_num;="" i++)="" {="">if (i != source) { cout < source=""><>' 到 ' < i=""><>' 的最短距離是：' < dist[i]=""><>'，路徑是：' < i;="">int t = path[i]; while (t != source) { cout <>'--' < t;="" t="path[t];" }="">cout <>'--' < source=""><>endl; } } return 0;}輸入數(shù)據(jù)，結(jié)果為：
請(qǐng)輸入圖的頂點(diǎn)數(shù)（100）：5請(qǐng)輸入圖的邊數(shù)：7請(qǐng)輸入邊的信息：0 1 30 2 10 3 21 3 32 3 23 4 32 4 3請(qǐng)輸入源點(diǎn)（5）：00 到 1 的最短距離是：3，路徑是：1--00 到 2 的最短距離是：1，路徑是：2--00 到 3 的最短距離是：2，路徑是：3--00 到 4 的最短距離是：4，路徑是：4--2--0設(shè)圖的邊數(shù)為m，頂點(diǎn)數(shù)為n。
Dijkstra算法最簡(jiǎn)單的實(shí)現(xiàn)方法是用一個(gè)數(shù)組來(lái)存儲(chǔ)所有頂點(diǎn)的dist[]（即本程序采用的策略），所以搜索dist[]中最小元素的運(yùn)算需要線性搜索$O(n)$。這樣的話算法的運(yùn)行時(shí)間是$O(n^2)$。
對(duì)于邊數(shù)遠(yuǎn)少于$n^2$的稀疏圖來(lái)說，我們可以用鄰接表來(lái)更有效的實(shí)現(xiàn)該算法，同時(shí)需要將一個(gè)二叉堆或者斐波納契堆用作優(yōu)先隊(duì)列來(lái)查找最小的頂點(diǎn)。當(dāng)用到二叉堆的時(shí)候，算法所需的時(shí)間為 $O((m+n)logn)$，斐波納契堆能稍微提高一些性能，讓算法運(yùn)行時(shí)間達(dá)到$O(m+nlogn)$。然而，使用斐波納契堆進(jìn)行編程，常常會(huì)由于算法常數(shù)過大而導(dǎo)致速度沒有顯著提高。
關(guān)于$O((m+n)logn)$的由來(lái)，我簡(jiǎn)單的證明了下：
dist[]數(shù)組調(diào)整成最小堆，需要$O(n)$的時(shí)間；dist[]的改變，因此還需要$O(logn)$的時(shí)間來(lái)進(jìn)行最小堆的重新調(diào)整（從當(dāng)前dist[]改變的位置往上調(diào)整）。綜上所述：總的時(shí)間復(fù)雜度為：$O(n)+O(nlogn)+O(mlogn)=O((m+n)logn)$
最后簡(jiǎn)單說下Dijkstra優(yōu)化時(shí)二叉堆的兩種實(shí)現(xiàn)方式：
dist[]壓在一個(gè)結(jié)構(gòu)體再放進(jìn)隊(duì)列里；heap[]，存儲(chǔ)頂點(diǎn)序號(hào)，再用一個(gè)數(shù)組pos[]記錄第i個(gè)頂點(diǎn)在堆中的位置。相比之下，前者的編碼難度較低，因此在平時(shí)編程甚至算法競(jìng)賽中，都是首選。
Dijkstra算法有個(gè)巨大的缺陷，請(qǐng)考慮下面這幅圖：
u→v間存在一條負(fù)權(quán)回路（所謂的負(fù)權(quán)回路，維基和百科并未收錄其名詞，但從網(wǎng)上的一致態(tài)度來(lái)看，其含義為：如果存在一個(gè)環(huán)（從某個(gè)點(diǎn)出發(fā)又回到自己的路徑），而且這個(gè)環(huán)上所有權(quán)值之和是負(fù)數(shù)，那這就是一個(gè)負(fù)權(quán)環(huán)，也叫負(fù)權(quán)回路），那么只要無(wú)限次地走這條負(fù)權(quán)回路，便可以無(wú)限制地減少它的最短路徑權(quán)值，這就變相地說明最短路徑不存在。一個(gè)不存在最短路徑的圖，Dijkstra算法無(wú)法檢測(cè)出這個(gè)問題，其最后求解的dist[]也是錯(cuò)的。
那么對(duì)于上述的“一個(gè)不存在最短路徑的圖”，我們?cè)撚檬裁捶椒▉?lái)解決呢？請(qǐng)接著看本系列第二篇文章。
聯(lián)系客服
