優(yōu)先級隊列:priority_queue,經(jīng)過實驗之后發(fā)現(xiàn)默認是首先輸出最大的元素，現(xiàn)在想讓隊頭為最小的元素，需要進行運算符重載
此算法尋找源點到與它連接的所有頂點的最短路徑

運算符重載：

struct Node {int u, step;Node() {};Node(int a, int sp) {u = a; step = sp;//u為頂點，step為源點到頂點u的最短路徑 }bool operator < (const Node& a)const { // 重載 <return step > a.step;} };

注意這樣重載以后operator<為成員函數(shù)，再用pop出隊時首先出的是step最小的結點
總代碼：

#include <iostream> #include<cstring> #include<queue> #include<algorithm> #include<windows.h> #define INF 0x7fffffff const int N = 100; // 城市的個數(shù)可修改int map[N][N], dist[N], n, m; int flag[N]; struct Node {int u, step;Node() {};Node(int a, int sp) {u = a; step = sp;}bool operator < (const Node& a)const { // 重載 <return step > a.step;} }; void Dijkstra(int st) {priority_queue <Node> Q; // 優(yōu)先隊列優(yōu)化Q.push(Node(st, 0));memset(flag, 0, sizeof(flag));//初始化flag數(shù)組為0for (int i = 1; i <= n; ++i)dist[i] = INF; // 初始化所有距離為，無窮大dist[st] = 0;while (!Q.empty()){Node it = Q.top();//優(yōu)先隊列隊頭元素為最小值Q.pop();int t = it.u;if (flag[t])//說明已經(jīng)找到了最短距離，該結點是隊列里面的重復元素continue;flag[t] = 1;for (int i = 1; i <= n; i++){if (!flag[i] && map[t][i] < INF) { // 判斷與當前點有關系的點，并且自己不能到自己if (dist[i] > dist[t] + map[t][i]){ // 求距離當前點的每個點的最短距離,進行松弛操作dist[i] = dist[t] + map[t][i];Q.push(Node(i, dist[i]));// 把更新后的最短距離壓入優(yōu)先隊列，注意：里面的元素有重復}}}} } int main(){int u, v, w, st;system("color 0d");//設置背景及字體顏色cout << "請輸入城市的個數(shù)：" << endl;cin >> n;cout << "請輸入城市之間的路線的個數(shù)：" << endl;cin >> m;for (int i = 1; i <= n; i++)//初始化圖的鄰接矩陣for (int j = 1; j <= n; j++){map[i][j] = INF;//初始化鄰接矩陣為無窮大}cout << "請輸入城市之間u,v的路線以及距離w：" << endl;while (m--){cin >> u >> v >> w;map[u][v] = min(map[u][v], w); //鄰接矩陣儲存，保留最小的距離}cout << "請輸入小明所在的位置：" << endl; ;cin >> st;Dijkstra(st);cout << "小明所在的位置：" << st << endl;for (int i = 1; i <= n; i++){cout << "小明:" << st << "--->" << "要去的位置：" << i;if (dist[i] == INF)cout << "sorry,無路可達" << endl;elsecout << " 最短距離為：" << dist[i] << endl;}return 0; }

注意這個：
if (flag[t])//說明已經(jīng)找到了最短距離，該結點是隊列里面的重復元素
continue;
已經(jīng)找到了從源點到t的最短距離，結束此輪循環(huán)，開始下一輪循環(huán)，出隊Q的下一個頂點，尋找源點到下一個頂點的最小路徑

摘錄自書籍【趣學算法】第2.5節(jié)

總結

以上是生活随笔為你收集整理的【算法学习笔记】 图（四）用优先级队列优化Dijkstra算法求最短路径（邻接矩阵存储）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。