在上次的博客中，我們解決了使用最小的邊讓各個頂點連通（最小生成樹）
這次我們要解決的問題是現在有一個圖，我們要找到一條路，使得從一個頂點到另一個頂點路徑權值之和最小（比如：找到從小潮到胖迪最短的一條路徑）：

我們可以看出來，小潮->小傲->胖迪這條路徑是最短的。

而我們今天學的算法，Dijkstra，就是完成這樣的工作的：

Dijkstra算法

Dijkstra算法是一種用于尋找圖中兩個節點之間的最短路徑的算法，由荷蘭計算機科學家Edsger W. Dijkstra于1956年發明。該算法的基本思想是使用貪心策略，從起始節點開始，逐步擴展到距離它最近的未訪問過的節點，直到目標節點被訪問。

以下是Dijkstra算法的基本步驟：

1. 初始化：將起點到所有其他節點的距離設為無窮大（表示還未計算），除了起點到自身的距離為0。創建一個空的已訪問節點集合和一個包含所有節點的未訪問節點集合。

2. 從未訪問節點集合中選擇距離起點最近的節點，將其標記為已訪問，并更新其鄰接節點的距離。如果某個鄰接節點的距離通過當前節點更短，則更新該鄰接節點的距離。

3. 重復步驟2，直到找到目標節點或未訪問節點集合為空。

4. 如果找到了目標節點，則返回從起點到目標節點的最短路徑；否則，說明起點和目標節點之間不存在路徑。

需要注意的是，Dijkstra算法只適用于沒有負權重邊的圖，因為負權重邊會導致算法無法正確地確定最短路徑。此外，Dijkstra算法的時間復雜度為O(ElogV)，其中E表示邊的數量，V表示節點的數量。在實際應用中，可以使用優先隊列等數據結構來優化算法的時間復雜度。

我們將上面的圖改造復雜一點，這樣可以看出Dijkstra算法的高效：

void TestGraph2(){string a[] = {"海皇","高斯","小傲","小潮","胖迪","小楊","皖皖"};Graph<string, int,INT_MAX, false> g1(a, sizeof(a)/sizeof(a[0]));g1.AddEdge("小潮", "小傲", 30);g1.AddEdge("小潮", "高斯", 83);g1.AddEdge("小潮", "海皇", 34);g1.AddEdge("胖迪", "海皇", 78);g1.AddEdge("胖迪", "小傲", 76);g1.AddEdge("小楊", "皖皖", 54);g1.AddEdge("小楊", "高斯", 48);g1.AddEdge("高斯", "皖皖", 55);g1.AddEdge("胖迪", "高斯", 70);g1.AddEdge("小傲", "海皇", 3);g1.Print();cout << endl;}

劃分集合

Dijkstra算法中，提到我們要劃分集合一個是訪問過的集合，一個是沒有被訪問過的集合，假設我們從小潮開始：

我們可以用一個bool的數組，訪問過了的標記為true，沒有為false。
假設我們要從小潮到胖迪，我們要計算路徑之和，我們還需要一個數組存放到各個頂點邊的權值：

同時，如果我們想打印路徑出來，我們還要一個數組存放路徑（這里有點像并查集里面的操作）：

模擬過程

假設我們從小潮開始，各個數組情況如下：

現在，掃描跟小潮相連的邊，最小的權值相關結點標記：

現在我們從小傲出發，發現海皇近，跳到海皇，發現總路徑之和為33，比原來34小，故更新，并標記：

我們代碼實現一下：

    void Dijkstra(const V& srci, vector<W>& dest, vector<int>& parentPath ){// 將源節點轉換為其在頂點列表中的索引int srcIndex = FindSrci(srci);// 初始化parentPath向量，用于記錄最短路徑上的前驅節點，初始值為-1表示未訪問parentPath.resize(_vertex.size(), -1);// 初始化dest向量，用于記錄從源節點到每個節點的最小距離，初始值為最大權重MAX_Wdest.resize(_vertex.size(), MAX_W);// 給源節點賦值為0，表示從源節點到自身距離為0dest[srcIndex] = W();// 初始化一個布爾型向量，用于記錄每個節點是否已被訪問，初始值為falsevector<bool> isVisted;isVisted.resize(_vertex.size(), false);// 主循環，迭代次數為頂點數for (size_t i = 0; i < _vertex.size(); i++){// 初始化最小距離為最大權重MAX_WW min = MAX_W;size_t u = srcIndex;// 尋找未被訪問且具有最小dest值的節點ufor (size_t j = 0; j < _vertex.size(); j++){if (isVisted[j] == false && dest[j] < min){min = dest[j];u = j;}}// 標記節點u為已訪問isVisted[u] = true;// 對節點u的所有鄰居進行松弛操作for (size_t i = 0; i < _vertex.size(); i++){// 只處理未被訪問的鄰居，并且存在從u到i的邊（_matrix[u][i] != MAX_W）if (isVisted[i] == false && _matrix[u][i] != MAX_W&& dest[u] + _matrix[u][i] < dest[i]){// 更新從源節點到節點i的最小距離dest[i] = dest[u] + _matrix[u][i];// 更新節點i的前驅節點為uparentPath[i] = u;}}}}

打印路徑

打印路徑記得一點，最后我們要逆置一下：

    // 打印從源節點到所有其他節點的最短路徑void PrintShortestPath(const V& src, const vector<W>& dist, const vector<int>& parentPath){// 將源節點轉換為其在頂點列表中的索引size_t srcIndex = FindSrci(src);// 遍歷所有頂點for (size_t i = 0; i < _vertex.size(); i++){// 跳過源節點本身if (i == srcIndex)continue;// 創建一個vector，用于存儲從目標節點到源節點的路徑vector<int> path;// 當前處理的節點初始化為目標節點size_t current = i;// 從目標節點出發，回溯到源節點，構建路徑while (current != srcIndex){// 將當前節點添加到路徑vector中path.push_back(current);// 將當前節點設置為其前驅節點，繼續回溯current = parentPath[current];}// 最后將源節點添加到路徑vector中path.push_back(srcIndex);// 翻轉路徑vector，使得路徑順序從源節點到目標節點reverse(path.begin(), path.end());// 輸出路徑和對應的最短距離for (auto node : path){// 輸出路徑中的每個節點cout << _vertex[node] << "->";}// 輸出從源節點到目標節點的最短距離cout << dist[i] << endl;}}