目錄
- 傳統藝能😎
- 問題背景🤔
- 思路🤔
- 代碼實作🤔
傳統藝能😎
小編是雙非大學大二菜鳥不贅述，歡迎米娜桑來指點江山哦
🎉🎉非科班轉碼社群誠邀您入駐🎉🎉
小夥伴們，滿懷希望，所向披靡，打碼一路向北
一個人的單打獨鬥不如一群人的砥砺前行
這是和夢想合夥人組建的社群，誠邀各位有志之士的加入！！
社群使用者好文均加精（“标兵”文章字數2000+加精，“達人”文章字數1500+加精）
直達： 社群連結點我
問題背景🤔
由多個節點多個連結的邊組成的圖，圖中某個頂點出發到達另外一個頂點的所經過的邊的權重最小的一條路徑（權重代表該路徑長度），稱為
解決這類問題有 3 種算法：
Dijkstra算法（迪傑斯特拉算法）
Floyd算法（弗洛伊德算法）
SPFA算法
dj 算法是非常常見且面試題出場率比較高的，但是缺點就是不支援負數權重，且下一次查找的方向不确定，算法的特點就是使用了廣度優先搜尋解決賦權有向圖或者無向圖的單源最短路徑問題，算法最終得到一個最短路徑樹，該算法常作為路由算法或其他圖算法的一個子子產品
思路🤔
比如要計算節點 0 到節點 4 的最短路徑，最短路徑采取
貪心算法
的政策，我們假設某一點無法到達的路徑的長度是 ∞ 大，則初始化時所有點我們都初始化為 ∞
首先節點 0 自己到自己距離一定是 0，是以 0 節點的值覆寫為 0，然後找到所有節點中距離最小的節點，沒錯就是我自己，于是将 0 标記為最短路徑中的節點 。
接着更新 0 節點的鄰接節點 1 和 7 的距離，他們的權重是 4 和 8，因為小于 ∞ 路徑長更新為4，8，此時節點 1 和節點 7 的前面節點就是節點 0，
這個過程有個專業術語叫做“松弛”，即 v0 頂點到 v1 頂點的路程即 dis[1] = 4，通過 <v0,v1> 這條邊松弛成功
。這便是 Dijkstra 算法的主要思想：通過“邊”來松弛v1頂點到其餘各個頂點的路程
接着又從未标記節點中，即剩下節點中找到距離出發點最小的節點，是節點 1 ，然後标記節點 1 為最短路徑中的節點。繼續更新節點 1 的鄰接節點 2 和 7
首先節點 1 到節點節點 2 的距離是 8，從 0 開始的路徑
v0–v1–v2
的長度就是 12，此時更新節點 2 的距離就是 12，他的前面點是節點 1；同理另一條路徑
v0–v1–v7
路徑長 15 ，因為這個路徑要大于 7 本來的距離（8），是以不更新
繼續在剩下節點中尋找最小節點，就是節點 7 ，把節點 7 放進最短路徑節點，接着更新 7 的鄰接節點：節點 8 和節點 6。
v0–v7–v8
長度為 15，
v0–v7–v6
長度為 9，此時他們都比 ∞ 小進行更新，他們前面點都是節點 7。
重複如上步驟就是本算法的核心思想，其實我們細看的話就分為兩步：
- 每次從未标記節點選出最小值節點，标記到最小路徑集合中
- 計算剛加入的最小值節點 A 到某個鄰接節點 B 的距離，即 A （此時 A 已經包含了之前路徑的和）+ A 到 B 的距離，如果結果小于 B 本身的距離，就更新 B 的值和前面點
循環這個過程，直到終點被标記。尋着這個規律，我們把剩下的路走完來示範一下：
在未标記節點中找到最小節點 6，标記為最小路徑中的節點，找到 6 的鄰接節點：節點 8 和節點 5，
v0–v7–v6–v5
路徑長為 11，小于 ∞ 是以進行更新；
v0–v7–v6–v8
路徑長為 15，和原來一樣就不做更新了
接着尋找最短距離節點，是 5 進行标記放入最短路徑點集合，這時他的鄰接節點有三個：
經過計算，節點 2，3，4 的路徑長為 15，25，21，因為原來 2 節點為 12，是以不進行更新，而 3,4 節點更新成為 25，21。
那麼接下來最短節點就是 2，他的鄰接節點是節點 8 和節點 3，節點 5 因為标記過了，是以不需要标記節點 5 了，路徑
v2–v3
長度 19，路徑
v2–v5
長度 14，兩個路徑都要更新距離和前面點。
接下來最短距離節點是 8，他的鄰接節點都已經被标記，無需更新；然後最短距離節點就是 3，更新未被标記的鄰接節點 4，
v3–v4
的路徑長度為 28，28 大于目前本身的 21，是以不做更新。
最後将未被标記的節點 4 标記，更新完畢，得出結論：從出發點 0 開始目的地節點 4 節點的最短距離就是 21
此時的最短路徑就是将上麥很從上到下的前面點一一連結起來即可：
代碼實作🤔
此時我們初始化一個數組 dis 來儲存起點到各個點的最短距離和一個儲存已經找到了最短路徑的點（或者稱之為前面點）的集合即可
void Graph_DG::Dijkstra(int begin){
//初始化 dis 數組
int i;
for (i = 0; i < this->vexnum; i++) {
//設定目前的路徑
dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
dis[i].value = arc[begin - 1][i];
}
//設定起點的到起點的路徑為0
dis[begin - 1].value = 0;
dis[begin - 1].visit = true;
int count = 1;
//計算剩餘的頂點的最短路徑（剩餘this->vexnum-1個頂點）
while (count != this->vexnum) {
//temp用于儲存目前dis數組中最小的那個下标
//min記錄的目前的最小值
int temp=0;
int min = INT_MAX;
for (i = 0; i < this->vexnum; i++) {
if (!dis[i].visit && dis[i].value<min) {
min = dis[i].value;
temp = i;
}
}
//cout << temp + 1 << " "<<min << endl;
//把temp對應的頂點加入到已經找到的最短路徑的集合中
dis[temp].visit = true;
++count;
for (i = 0; i < this->vexnum; i++) {
//注意這裡的條件判斷INT_MAX必須加，不然會出現溢出異常
if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
//如果新得到的邊可以影響其他的頂點，那就更新它的最短路徑和長度
dis[i].value = dis[temp].value + arc[temp][i];
dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);
}
}
}