??迪杰特斯拉還是比較常用的最短路徑算法。之前學數據結構時寫的代碼很冗余，總是記不住。今天有時間，整理出一個簡練的模板吧！
??實現的方式對應了優先隊列，模板中包括建圖的方法（其實哪種都可以）。本文用的是：

vector< unordered_map<int, int>> graph(n); // 本質是鄰接表

??模板如下：

void DIJ() {/* 建圖，建圖方式有幾種,盡量使用鄰接表* 1.vector<vector<int>> graph(n) // 臨界矩陣* 2.vector<unordered_map<int,int>> // 鄰接表，map中first代表指向，second代表權值*/ // 假設有vector<vector<int>> edges提供邊的信息，[1,2,3]代表1->2，權值為3vector<unordered_map<int, int>> graph(n);for (int i=0; i<edges.size(); i++) {int u = edges[i][0];int v = edges[i][1];int w = edges[i][2];graph[u-1][v-1] = w; // -1的原因是索引從0開始graph[v-1][u-1] = w; // 看清問題是單向圖還是雙向圖，決定了寫幾個}vector<int> dis(n, INT_MAX);priority_queue<pair<int, int>, vector<pair<int, int> > > q;// 起點編號設置為startdis[start] = 0;q.push(start, 0);while (!q.empty()) {pair<int, int> tp = q.top();int id = tp.first;int distance = tp.second;q.pop();// 這里用指針吧，用graph[id][i].first會報錯，不知道為啥for (auto it=graph[id].begin(); it != graph[id].end(); it++) {int new_id = it->first;int new_distance = it->second;if (dis[id]+new_distance < dis[new_id]) {dis[new_id] = dis[id] + new_distance;q.push(make_pair(new_id, -dis[new_id])); // 傳入負值，實現從小到大排列 }}} } // dis數組中得到的就是起點到各個節點的最短距離了，如果不達就會是INT_MAX

??光說不練假把式，來兩道例題試試模板吧！

練習一：P1339 [USACO09OCT]Heat Wave G

P1339 [USACO09OCT]Heat Wave G

AC代碼如下：

#include<bits/stdc++.h> using namespace std;int main(void) {int n,m,s,t;cin >> n >> m >> s >> t;vector<unordered_map<int,int> > graph(n);for (int i=0; i<m; i++) {int u,v,w;cin >> u >> v >>w;graph[u-1][v-1] = w;graph[v-1][u-1] = w;}vector<int> dis(n, INT_MAX);priority_queue<pair<int, int>, vector<pair<int, int>>> q;dis[s-1] = 0;q.push(make_pair(s-1,0));while (!q.empty()) {pair<int, int> tp = q.top();int id = tp.first;int distance = tp.second;q.pop();for (auto it=graph[id].begin(); it != graph[id].end(); it++) {int new_id = it->first;int new_distance = it->second;if (dis[id] + new_distance < dis[new_id]) {dis[new_id] = dis[id] + new_distance;q.push(make_pair(new_id, -dis[new_id]));}}}cout << dis[t-1];return 0; }

練習二：P3371 【模板】單源最短路徑（弱化版）

P3371 【模板】單源最短路徑（弱化版）
??其實這個代碼沒有完全通過測試，但也是按照模板寫的呀。能夠通過樣例，不知道怎么回事，請路過的大神幫我解答一下吧。先附上代碼，說不定以后就會了呢？

代碼如下：

#include<bits/stdc++.h> using namespace std; int main(void) {int n, m, s;cin >> n >> m >> s;vector<unordered_map<int, int>> graph(n);for (int i=0; i<m; i++) {int u,v,w;cin >> u >> v >> w;graph[u-1][v-1] = w;}vector<int> dis(n, INT_MAX);priority_queue<pair<int,int>,vector<pair<int,int>>> q;dis[s-1] = 0;q.push(make_pair(s-1, 0));while (!q.empty()) {pair<int, int> pa = q.top();int id = pa.first;int distance = pa.second;q.pop();for (auto it=graph[id].begin(); it!=graph[id].end(); it++) {int new_id = it->first;int new_distance = it->second;if (dis[id]+new_distance < dis[new_id]) {dis[new_id] = dis[id]+new_distance;q.push(make_pair(new_id, -dis[new_id]));}}}for (int i=0; i<n; i++) {if (i != n-1)cout << dis[i] << " ";elsecout << dis[i];}return 0; }

??其實真正的圖論題DIJ只是其中的一部分，那就一部分一部分掌握，希望慢慢能解決大題吧hhh！

參考資料：
迪杰斯特拉算法詳解+模版+例題

因作者水平有限，如有錯誤之處請在下方評論區指正，謝謝！

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的优先队列实现迪杰特斯拉模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。