淺談圖論——迪杰斯特拉算法（leetcode例題，C++演示）
一、談一談圖論
如果你想問這個世界上什么算法是最牛逼的？博主是回答不上來的。但是，如果你問博主什么數(shù)據(jù)結(jié)構(gòu)是最牛逼？博主個人認為圖是最牛逼的數(shù)據(jù)結(jié)構(gòu)。因為很多的問題，都可以用圖這種數(shù)據(jù)結(jié)構(gòu)來表示。鏈表、樹這種數(shù)據(jù)結(jié)構(gòu)博主認為可以看成一種特殊的圖。所以，博主今天就想探討一下圖論的經(jīng)典算法——迪杰斯特拉算法，如果覺得有用的小伙伴可以點一個贊，愛學習的你們真棒！
二、什么是迪杰斯特拉算法？
我們不要被迪杰斯特拉算法的名字嚇到了，其實迪杰斯特拉的算法并不復雜。很多時候，傳統(tǒng)的并不復雜的算法往往在解決現(xiàn)實問題的時候有這良好的效果。首先我們要搞清楚迪杰斯特拉算法解決的單源最短路徑的問題。單源最短路徑問題是找到從圖中的一個固定頂點（稱為源點）到其他所有頂點的最短路徑。
迪杰斯特拉算法步驟如下：
-
初始化： 將源點到其他頂點的距離初始化為無窮大，源點到自身的距離初始化為0。同時，維護一個集合
S，其中包含已確定最短路徑的頂點，初始時S為空。 -
選擇距離最小的頂點： 從未確定最短路徑的頂點中選擇一個到源點距離最小的頂點，并將其標記為已確定最短路徑。將該頂點加入集合
S中。 -
更新距離： 對于新確定的頂點，遍歷其所有相鄰的頂點，更新這些頂點到源點的最短路徑估計值。如果通過新確定的頂點可以獲得更短的路徑，則更新相應(yīng)頂點到源點的距離值。
-
重復步驟2和步驟3： 重復選擇距離最小的頂點和更新距離的步驟，直到所有頂點的最短路徑都被確定。
迪杰斯特拉算法圖示如下（轉(zhuǎn)自知乎@鵝廠程序小哥）
原文鏈接：https://zhuanlan.zhihu.com/p/346558578
我們看出，迪杰斯特拉算法本質(zhì)是一個貪心算法，也就是多個局部最優(yōu)累計到全局最優(yōu)。因為我們每次找的都是未選取的點通過已選取的點到源點的最短路徑，或許還存在其他情況的更短路徑。所以，每次得到一個新的最短的路徑時，我們都需要將這個距離與現(xiàn)有的距離取小值作為最短的距離。
三、典型例題講解（leetcode）
為了更好的了解該算法，我們通過力扣的一道題目具體的實現(xiàn)迪杰斯特拉算法，題目鏈接。
有 n 個網(wǎng)絡(luò)節(jié)點，標記為 1 到 n。
給你一個列表 times，表示信號經(jīng)過 有向 邊的傳遞時間。 times[i] = (ui, vi, wi)，其中 ui 是源節(jié)點，vi 是目標節(jié)點， wi 是一個信號從源節(jié)點傳遞到目標節(jié)點的時間。
現(xiàn)在，從某個節(jié)點 K 發(fā)出一個信號。需要多久才能使所有節(jié)點都收到信號？如果不能使所有節(jié)點收到信號，返回 -1 。
示例 1：
輸入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
輸出：2
示例 2：
輸入：times = [[1,2,1]], n = 2, k = 1
輸出：1
示例 3：
輸入：times = [[1,2,1]], n = 2, k = 2
輸出：-1
提示：
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100- 所有
(ui, vi)對都 互不相同（即，不含重復邊）
我們分析一下這個題目。首先。這是一個有向圖問題，它希望我們找到從某一個源點發(fā)送信號到所有節(jié)點都收到信號的時間。那么，我們就可以把問題轉(zhuǎn)化成單源最短路徑問題。我們只需要取某一源點到其他節(jié)點的最短路徑中的最大值，就可以解決這個例題。這是博主的思路，相當于用迪杰斯特拉算法找到源點到其他所有節(jié)點的最短路徑，再進行比較，如果有更好的思路歡迎交流。
四、博主代碼詳解（C++）
接下來，我們要分析代碼的實現(xiàn)了。這是博主自己寫的代碼，不是很成熟，AC是沒問題的。首先奉上所有的代碼，我們接下來對每一塊進行分析。
class Solution {
public:
//尋找距離
vector<int> find_distance(vector<vector<int>>& times, vector<int>& flag,
int n, int k) {
vector<int> distance(n, 10000);
distance[k - 1] = 0;
flag[k - 1] = 1;
for (int i = 0; i < times.size(); i++) {
if (times[i][0] == k) {
distance[times[i][1] - 1] = times[i][2];
}
}
return distance;
}
//更新距離
vector<int> update_distance(vector<vector<int>>& times, vector<int>& flag,
vector<int>& distance, int n, int k) {
vector<int> temp = find_distance(times, flag, n, k);
int m;
for (int i = 0; i < n; i++) {
if (temp[i] < 10000 && flag[i]!=1) {
m = distance[k-1] + temp[i];
distance[i] = fmin(m, distance[i]);
}
}
return distance;
}
//尋找下一個節(jié)點
int find_next(vector<int> distance, vector<int>& flag, int n) {
int min_index;
for (int i = 0; i < n; i++) {
if (flag[i] == 1)
distance[i] = 10000;
}
min_index = min_element(distance.begin(), distance.end()) - distance.begin();
if (distance[min_index] == 10000)
return -1;
return min_index + 1;
}
//實現(xiàn)的主邏輯函數(shù)
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
int min_index;
vector<int> distance;
vector<int> flag(n, 0);
distance = find_distance(times, flag, n, k);
min_index = find_next(distance, flag, n);
while (min_index != -1) {
distance = update_distance(times, flag, distance, n, min_index);
min_index = find_next(distance, flag, n);
}
auto it = find(flag.begin(), flag.end(), 0);
if (it != flag.end())
return -1;
else
return *max_element(distance.begin(), distance.end());
}
};
這是整體的代碼結(jié)構(gòu)，我們接下會分析每個函數(shù)的作用。首先，我先聲明一下flag相當于是一個n維全局變量，用于判斷源點是否找到了對所有點的最短路徑，0為未找到，1為找到。
1、find_distance函數(shù)
vector<int> find_distance(vector<vector<int>>& times, vector<int>& flag,
int n, int k) {
vector<int> distance(n, 10000);
distance[k - 1] = 0;
flag[k - 1] = 1;
for (int i = 0; i < times.size(); i++) {
if (times[i][0] == k) {
distance[times[i][1] - 1] = times[i][2];
}
}
return distance;
}
首先，這個函數(shù)的作用是找到某一點到其他點的距離，如果是非相鄰的節(jié)點，則距離為10000（在本題中相當于無限大）。我們要知道該函數(shù)輸入四個變量，注意變量k是點的標號，不是索引。其次，該函數(shù)返回一個n維向量distance，具體的實現(xiàn)方法就是遍歷。
注意，只要我們使用find_distance函數(shù)作用于某一個點，說明這個點已經(jīng)存在一條到源點的路徑，所以要執(zhí)行flag[k - 1] = 1，講到后面會明白的。
2、update_distance函數(shù)
vector<int> update_distance(vector<vector<int>>& times, vector<int>& flag,
vector<int>& distance, int n, int k) {
vector<int> temp = find_distance(times, flag, n, k);
int m;
for (int i = 0; i < n; i++) {
if (temp[i] < 10000 && flag[i]!=1) {
m = distance[k-1] + temp[i];
distance[i] = fmin(m, distance[i]);
}
}
return distance;
}
update_distance函數(shù)傳入五個變量，其中此distance非彼distance，這也相當于一個n維全局變量，是源點到其他點的距離。這個函數(shù)的作用就是通過調(diào)用find_distance函數(shù)作用于某一已經(jīng)和源點之間存在最短路徑的點，找到它和相鄰點的距離，來更新源點到這個相鄰點的距離。
distance[i] = fmin(m, distance[i])這一句很重要，我們需要取新得到的距離和原來的距離的較小值，防止局部最優(yōu)影響到全局最優(yōu)。
3、find_next函數(shù)
int find_next(vector<int> distance, vector<int>& flag, int n) {
int min_index;
for (int i = 0; i < n; i++) {
if (flag[i] == 1)
distance[i] = 10000;
}
min_index = min_element(distance.begin(), distance.end()) - distance.begin();
if (distance[min_index] == 10000)
return -1;
return min_index + 1;
}
find_next函數(shù)的作用就是尋找update_distance函數(shù)所作用的下一個點。它接受四個變量，其中distance和flag都相當于一個全局變量。這里的distance是一個形參，不是實參，方便節(jié)省空間。具體的實現(xiàn)方法就是把所有已經(jīng)遍歷的點的距離置10000，再返回最小距離對應(yīng)的點的標號（不是索引，所以要加1）。
4、networkDelayTime函數(shù)
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
int min_index;
vector<int> distance;
vector<int> flag(n, 0);
distance = find_distance(times, flag, n, k);
min_index = find_next(distance, flag, n);
while (min_index != -1) {
distance = update_distance(times, flag, distance, n, min_index);
min_index = find_next(distance, flag, n);
}
auto it = find(flag.begin(), flag.end(), 0);
if (it != flag.end())
return -1;
else
return *max_element(distance.begin(), distance.end());
}
這是整個程序的主函數(shù)，首先我們使用find_distance函數(shù)作用于源點，初始化diatance向量。然后，我們初始下一個要找的點的標號，注意這里的index不是索引，是標號。
接著我們循環(huán)更新distance直到找不到min_index。如果flag向量含有0值，說明有的點到達不了，返回1。否則，返回distance中的最小值。這樣，問題就解決了。
五、官方題解代碼詳解（C++）
博主的代碼寫的太長了，水平還不到家，僅供參考，我們來看官方題解。
class Solution {
public:
int networkDelayTime(vector<vector<int>> ×, int n, int k) {
const int inf = INT_MAX / 2;
vector<vector<int>> g(n, vector<int>(n, inf));
for (auto &t : times) {
int x = t[0] - 1, y = t[1] - 1;
g[x][y] = t[2];
}
vector<int> dist(n, inf);
dist[k - 1] = 0;
vector<int> used(n);
for (int i = 0; i < n; ++i) {
int x = -1;
for (int y = 0; y < n; ++y) {
if (!used[y] && (x == -1 || dist[y] < dist[x])) {
x = y;
}
}
used[x] = true;
for (int y = 0; y < n; ++y) {
dist[y] = min(dist[y], dist[x] + g[x][y]);
}
}
int ans = *max_element(dist.begin(), dist.end());
return ans == inf ? -1 : ans;
}
};
作者：力扣官方題解
鏈接：https://leetcode.cn/problems/network-delay-time/solutions/909575/wang-luo-yan-chi-shi-jian-by-leetcode-so-6phc/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
官方題解首先把times轉(zhuǎn)化維一個矩陣儲存。官方題解的巧妙在于for循環(huán)的第一次肯定選取是源點，相當于對源點到其他點的距離做了初始化。
for (int y = 0; y < n; ++y) {
if (!used[y] && (x == -1 || dist[y] < dist[x])) {
x = y;
}
}
其中，這一段代碼是尋找下一個要處理的點。
for (int y = 0; y < n; ++y) {
dist[y] = min(dist[y], dist[x] + g[x][y]);
}
這一段代碼是更新距離。文章來源：http://www.zghlxwxcb.cn/news/detail-830230.html
循環(huán)總共找n次，保證了源點能到達的點都能找到。文章來源地址http://www.zghlxwxcb.cn/news/detail-830230.html
for (int y = 0; y < n; ++y) {
if (!used[y] && (x == -1 || dist[y] < dist[x])) {
x = y;
}
}
其中，這一段代碼是尋找下一個要處理的點。
for (int y = 0; y < n; ++y) {
dist[y] = min(dist[y], dist[x] + g[x][y]);
}
這一段代碼是更新距離。
循環(huán)總共找n次，保證了源點能到達的點都能找到。
到了這里，關(guān)于淺談圖論——迪杰斯特拉算法（leetcode例題，C++演示）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
