算法-圖-dijkstra 最短路徑

理論知識

dijkstra三部曲

樸素版dijkstra

模擬過程?

堆優化版dijksra

經典模版例題

Dijkstra求最短路 I ??

參加科學大會（第六期模擬筆試）--模版題

網絡延遲

ref

理論知識

????????最短路是圖論中的經典問題即：給出一個有向圖，一個起點，一個終點，問起點到終點的最短路徑。

????????dijkstra算法：在有權圖（權值非負數）中求從起點到其他節點的最短路徑算法。需要注意兩點：

dijkstra 算法可以同時求起點到所有節點的最短路徑
權值不能為負數

dijkstra三部曲

第一步，選源點到哪個節點近且該節點未被訪問過;（minDist數組里的數值，結合visited數組篩選出未訪問的節點）
第二步，該最近節點被標記訪問過;（更新visited數組）
第三步，更新非訪問節點到源點的距離（即更新minDist數組）。minDist數組用來記錄每一個節點距離源點的最小距離。（更新minDist數組）（初始化的時候就應該初始為最大值）

樸素版dijkstra

模擬過程?

????????①初始化：節點0 不做處理，統一從下標1 開始計算，源點（節點1）到自己的距離為0，所以 minDist[1] = 0；?此時所有節點都沒有被訪問過，所以 visited數組都為0。

? ? ? ? ②dijkstra 三部曲：

?? ??? ??

? ? ? ??

?? ? ?

? ??

?更新 minDist數組，即：源點（節點1）到 節點6 、節點3 和節點4【與當前被訪問節點2相連的節點】的距離。

源點到節點6的最短距離為5，小于原minDist[6]的數值max，更新minDist[6] = 5
源點到節點3的最短距離為3，小于原minDist[3]的數值4，更新minDist[3] = 3
源點到節點4的最短距離為6，小于原minDist[4]的數值max，更新minDist[4] = 6

源點到節點4的最短距離為5，小于原minDist[4]的數值6，更新minDist[4] = 5

...........

...........最終

????????節點1）到終點（節點7）的最短距離就是 minDist[7] ，按上面舉例講解來說，minDist[7] = 12，節點1 到節點7的最短路徑為 12。?

堆優化版dijksra

? ? ? ? 1、鄰接表結構存儲：?vector<vector<pair<int, int>>> adj(n + 1); // 鄰接表直接存儲邊

? ? ? ? 2、初始化最? 短距離數組和優先隊列，設定起點距離

????????使用小頂堆（priority_queue）存儲?<距離, 節點>?對，初始時將起點?(0, 1)?加入隊列

????????????????priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

? ? ? ? 3、主循環：通過優先隊列快速找到當前最短路徑節點，并更新鄰接節點。

????????????????

用到的數據結構：

?vector<vector<pair<int, int>>> adj(n + 1)
adj[1] = { {2, 2}, {3, 4} }; // 從 1 出發，有 1→2 (權2)，1→3 (權4)
adj[2] = { {3, 1}, {4, 7} }; // 從 2 出發，有 2→3 (權1)，2→4 (權7)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

動態維護當前擴展的最短路徑節點

經典模版例題

Dijkstra求最短路 I??

完整代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m;cin>>n>>m;vector<vector<int>> grid(n+1,vector<int>(n+1,INT_MAX));for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;if (z < grid[x][y]) {  // 處理重邊，保留最小權重grid[x][y] = z;}}vector<int> minDist(n+1,INT_MAX);vector<bool> visited(n+1,false);int start=1;minDist[start]=0;for(int i=1;i<=n;i++){int minval=INT_MAX;int cur=-1;for(int j=1;j<=n;j++){if(!visited[j]&&minDist[j]<minval){minval=minDist[j];cur=j;}}if (cur == -1) break;  // 所有剩余節點不可達visited[cur]=true;for(int j=1;j<=n;j++){if(!visited[j]&&grid[cur][j]!=INT_MAX&&grid[cur][j]+minDist[cur]<minDist[j]){minDist[j]=minDist[cur]+grid[cur][j];}}}if(minDist[n]==INT_MAX) cout<<"-1";else cout<<minDist[n];return 0;
}

注意重邊？？？？？！！！！??

堆優化版：

#include <bits/stdc++.h>
using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<pair<int, int>>> adj(n + 1); // 鄰接表直接存儲邊// 讀取邊并構建鄰接表（無需預處理二維數組）for (int i = 0; i < m; ++i) {int x, y, z;cin >> x >> y >> z;adj[x].emplace_back(y, z); // 直接添加所有邊}// Dijkstra算法vector<int> dist(n + 1, INT_MAX);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;dist[1] = 0;pq.push({0, 1});while (!pq.empty()) {auto [d, u] = pq.top();pq.pop();if (d > dist[u]) continue; // 跳過過時記錄for (auto [v, w] : adj[u]) {if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.push({dist[v], v});}}}// 輸出結果cout << (dist[n] == INT_MAX ? -1 : dist[n]);return 0;
}

參加科學大會（第六期模擬筆試）--模版題

完整代碼：?（我真的好愛卡哥，代碼簡潔又易懂！！！！！）

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m;cin>>n>>m;//鄰接矩陣存儲vector<vector<int>> grid(n+1,vector<int>(n+1,INT_MAX));//初始化數值為INT_MAXfor(int i=0;i<m;i++) //輸入邊權{int s,e,v;cin>>s>>e>>v;grid[s][e]=v;//存儲邊權值}int start=1;//記錄源點，從哪個點開始走int end=n;//記錄終點vector<int> minDist(n+1,INT_MAX);//存儲每個點至源點的最小距離minDist[start]=0;//源點到自身距離為0；vector<bool> visited(n+1,false);//記錄該點是否被訪問過，初始化都沒有被訪問過//依次遍歷所有結點for(int i=1;i<=n;i++){int minval=INT_MAX;int cur=start;//記錄當前被訪問的點中哪個點距離源點最近//1、選距離源點最近&&沒有被訪問過的點for(int v=1;v<=n;v++){if(!visited[v]&&minDist[v]<minval){minval=minDist[v];cur=v;//記錄該最近結點的id}}//2、標記該最近結點beifnagwvisited[cur]=true;//3、更新其他非訪問節點到源點的距離（更新minDist數組）for(int v=1;v<=n;v++){//沒有被訪問過的、與 cur相連的、更新后minDist更小的if(!visited[v]&&grid[cur][v]!=INT_MAX &&minDist[v]>minDist[cur]+grid[cur][v])minDist[v]=minDist[cur]+grid[cur][v];}}//不能到達終點if(minDist[end]==INT_MAX) cout<<-1<<endl;else cout<<minDist[end]<<endl; //輸出到達終點的最短路徑return 0;}

堆優化版：

#include <bits/stdc++.h>
using namespace std;int main() {int n, m;cin >> n >> m;// 鄰接表存儲：adj[x]保存從x出發的所有邊，格式為<目標節點, 邊權>vector<vector<pair<int, int>>> adj(n + 1);// 處理輸入并保留最小邊權（處理重邊）vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));for (int i = 0; i < m; ++i) {int s, e, v;cin >> s >> e >> v;if (v < grid[s][e]) grid[s][e] = v;  // 僅保留最小權重}// 將鄰接矩陣轉換為鄰接表for (int x = 1; x <= n; ++x) {for (int y = 1; y <= n; ++y) {if (grid[x][y] != INT_MAX) {adj[x].push_back({y, grid[x][y]});}}}// Dijkstra堆優化實現vector<int> dist(n + 1, INT_MAX);        // 存儲起點到各節點的最短距離priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 小頂堆，格式<距離, 節點>dist[1] = 0;                             // 起點距離初始化為0pq.push({0, 1});                         // 將起點加入堆while (!pq.empty()) {auto [d, u] = pq.top();              // 取出當前距離最小的節點pq.pop();if (d > dist[u]) continue;           // 跳過過時的路徑記錄for (auto [v, w] : adj[u]) {         // 遍歷所有鄰接節點if (dist[v] > dist[u] + w) {     // 發現更短路徑dist[v] = dist[u] + w;       // 更新距離pq.push({dist[v], v});       // 將新距離加入堆}}}// 輸出結果：終點不可達則輸出-1cout << (dist[n] == INT_MAX ? -1 : dist[n]) << endl;return 0;
}

網絡延遲

#include<bits/stdc++.h>
using namespace std;int main() {int n, k, m;cin >> n >> k >> m;vector<vector<int>> grid(n+1, vector<int>(n+1, INT_MAX));for(int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;grid[u][v] = w; // 存儲有向邊}vector<int> minDist(n+1, INT_MAX);vector<bool> visited(n+1, false);minDist[k] = 0; // 起點距離為0for(int i = 1; i <= n; ++i) {int minVal = INT_MAX;int cur = -1;// 尋找當前未訪問的最小距離節點for(int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}// 所有剩余節點不可達if (cur == -1) break;visited[cur] = true;// 更新相鄰節點for(int v = 1; v <= n; ++v) {if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] != INT_MAX) {if (minDist[v] > minDist[cur] + grid[cur][v]) {minDist[v] = minDist[cur] + grid[cur][v];}}}}int maxTime = 0;for(int i = 1; i <= n; ++i) {if (minDist[i] == INT_MAX) {cout << -1 << endl;return 0;}maxTime = max(maxTime, minDist[i]);}cout << maxTime << endl;return 0;
}

堆優化版：?

#include <bits/stdc++.h>
using namespace std;int main() {int n, k, m;cin >> n >> k >> m;vector<vector<pair<int, int>>> adj(n + 1); // 鄰接表存儲圖for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;adj[u].emplace_back(v, w);}// Dijkstra算法vector<int> dist(n + 1, INT_MAX);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;dist[k] = 0;pq.push({0, k});while (!pq.empty()) {auto [d, u] = pq.top();pq.pop();if (d > dist[u]) continue;for (auto [v, w] : adj[u]) {if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.push({dist[v], v});}}}int maxTime = *max_element(dist.begin() + 1, dist.end());cout << (maxTime == INT_MAX ? -1 : maxTime) << endl;return 0;
}