? ? ? ? 大家好，我們昨天講解的是拓撲排序與Dijkstra算法的樸素版，其實我們大致了解了兩種算法的代碼實現，我們通過上次博客了解到拓撲排序其實是可以判斷圖里是否存在環，而Dijkstra算法則使用于非負邊權最短路的求解，今天我們繼續昨天的內容，我們首先要了解的就是Djikstra算法的堆優化版本，這個其實我以前就了解過這個算法，還有一個就是Bellman_ford 算法，這個其實就彌補了Djikstra算法不能求解帶負邊權的最短路，那么很明顯我們今天的主題就是最短路算法了。

第一部分 dijkstra（堆優化版）

? ? ? ? 這個我們首先要區分我們上次講過的樸素版，我們就來看看這個算法是如何實現的？其實關于圖的存儲方式我們以前就有講解過主要有兩種方法，一種是鄰接矩陣法還有一種是鄰接表法，我們說鄰接表法對于稀疏圖的存儲，只需要存儲邊，空間利用率高，遍歷節點鏈接情況相對容易，這里我們就使用鄰接表來存儲圖，第一步：選源點到哪個節點近且該節點未被訪問過，第二步：該最近節點被標記訪問過，第三步：更新非訪問節點到源點的距離（即更新minDist數組），其實我們在前面的樸素版的dijkstra算法就有提到過這個三部曲，但在那個版本的算法里這三部曲是套在一個 for 循環里，為什么？因為我們是從節點的角度來解決問題。那么當從 邊 的角度出發， 在處理 三部曲里的第一步（選源點到哪個節點近且該節點未被訪問過）的時候 ，我們可以不用去遍歷所有節點了。而且 直接把 邊（帶權值）加入到 小頂堆（利用堆來自動排序），那么每次我們從 堆頂里 取出 邊 自然就是 距離源點最近的節點所在的邊。這個思路我感覺是非常妙，堆是一種很常用的數據結構，它具備排序的功能，當然可能有的語言默認大根堆，有的默認小根堆，我們這里要使用小根堆，因為我們要尋找的是最短路徑，這樣我們就不需要兩層for循環來尋找最近的節點了。

? ? ? ?這樣有了大致的思路以后，我們就可以逐漸嘗試去寫代碼，但是代碼一開始我們就遇到了麻煩，我們應該如何表示鄰接表呢？在vector<list<int>> grid(n + 1);?中 就不能使用int了，而是需要一個鍵值對 來存兩個數字，一個數表示節點，一個數表示 指向該節點的這條邊的權值。我們的堆優化版依舊是我們的三部曲，那么三部曲中的第一步（選源點到哪個節點近且該節點未被訪問過），我們如何選？我們要選擇距離源點近的節點（即：該邊的權值最小），所以 我們需要一個 小頂堆 來幫我們對邊的權值排序，每次從小頂堆堆頂 取邊就是權值最小的邊。這個寫起C++代碼來也是很難，后面我會一并給出，接下來的更新過程與我們以前是類似的，我就不多說了，我們直接給出大家代碼：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std; 
// 小頂堆
class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};
// 定義一個結構體來表示帶權重的邊
struct Edge {int to;  // 鄰接頂點int val; // 邊的權重Edge(int t, int w): to(t), val(w) {}  // 構造函數
};int main() {int n, m, p1, p2, val;cin >> n >> m;vector<list<Edge>> grid(n + 1);for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val; // p1 指向 p2，權值為 valgrid[p1].push_back(Edge(p2, val));}int start = 1;  // 起點int end = n;    // 終點// 存儲從源點到每個節點的最短距離std::vector<int> minDist(n + 1, INT_MAX);// 記錄頂點是否被訪問過std::vector<bool> visited(n + 1, false); // 優先隊列中存放 pair<節點，源點到該節點的權值>priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;// 初始化隊列，源點到源點的距離為0，所以初始為0pq.push(pair<int, int>(start, 0)); minDist[start] = 0;  // 起始點到自身的距離為0while (!pq.empty()) {// 1. 第一步，選源點到哪個節點近且該節點未被訪問過 （通過優先級隊列來實現）// <節點， 源點到該節點的距離>pair<int, int> cur = pq.top(); pq.pop();if (visited[cur.first]) continue;// 2. 第二步，該最近節點被標記訪問過visited[cur.first] = true;// 3. 第三步，更新非訪問節點到源點的距離（即更新minDist數組）for (Edge edge : grid[cur.first]) { // 遍歷 cur指向的節點，cur指向的節點為 edge// cur指向的節點edge.to，這條邊的權值為 edge.valif (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDistminDist[edge.to] = minDist[cur.first] + edge.val;pq.push(pair<int, int>(edge.to, minDist[edge.to]));}}}if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到達終點else cout << minDist[end] << endl; // 到達終點最短路徑
}

? ? ?這里定義小頂堆要注意，還要注意我們的pair表示的是什么。

第二部分 Bellman_ford 算法

? ? ? ?Bellman_ford算法的核心思想是 對所有邊進行松弛n-1次操作（n為節點數量），從而求得目標最短路，這個相當重要，這個松弛是什么意思，這里可以這樣理解：

? ? ? ? minDist[B] 表示 到達B節點 最小權值，minDist[B] 有哪些狀態可以推出來？狀態一： minDist[A] + value 可以推出 minDist[B] 狀態二： minDist[B]本身就有權值 （可能是其他邊鏈接的節點B 例如節點C，以至于 minDist[B]記錄了其他邊到minDist[B]的權值），這樣的話minDist[B] 應為如何取舍。本題我們要求最小權值，那么 這兩個狀態我們就取最小的，也就是說，如果 通過 A 到 B 這條邊可以獲得更短的到達B節點的路徑，即如果?minDist[B] > minDist[A] + value，那么我們就更新?minDist[B] = minDist[A] + value?，這個過程就叫做 “松弛” 。這個其實不就還是更新最短路徑，這個是不是讓大家想起我們以前學過的動態規劃，動態規劃里面不就經常有取最小值的操作。接下來我可以簡單給大家模擬一下松弛的操作：首先對所有邊松弛一次，相當于計算 起點到達 與起點一條邊相連的節點 的最短距離。

?

? ? ? ??大家可以先看一下上面的圖，邊：節點1 -> 節點2，權值為1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 ，接下來邊：節點2 -> 節點5，權值為2 ，minDist[5] > minDist[2] + 2 （經過上面的計算minDist[2]已經不是默認值，而是 1），更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 ，但是節點5 -> 節點3，權值為1 ，minDist[5] 還是默認數值max，所以不能基于節點5去更新節點3 ，后續的都是這樣，我就不給大家一一演示了。

? ? ? 最后我們可以嘗試給出完整代碼：

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid;// 將所有邊保存起來for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;// p1 指向 p2，權值為 valgrid.push_back({p1, p2, val});}int start = 1;  // 起點int end = n;    // 終點vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;for (int i = 1; i < n; i++) { // 對所有邊 松弛 n-1 次for (vector<int> &side : grid) { // 每一次松弛，都是對所有邊進行松弛int from = side[0]; // 邊的出發點int to = side[1]; // 邊的到達點int price = side[2]; // 邊的權值// 松弛操作 // minDist[from] != INT_MAX 防止從未計算過的節點出發if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price;  }}}if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到達終點else cout << minDist[end] << endl; // 到達終點最短路徑}

? ? ? ? ?這就是我們的Bellman_ford算法，大家一刷稍微有一些了解就可以，暫時不必追根究底。

今日總結

? ? ? ? ?今天我們主要講解的都是最短路的相關算法，有的可以用于邊權為負數的情況，有的不可以，大家對這些算法如果有困難，一方面理解不容易另一方面代碼太長，大家可以慢慢消化，我們今天就講解到這里，我們下次博客再見！