dijkstra單源最短路徑算法不允許邊權(quán)值為負(fù)，適用的圖范圍可以很大。
代碼如下：

#include <iostream> #include <queue> #include <vector> #include <string> using namespace std; const int N = 1e8; bool done[N]; int dis[N]; const int INF = 1 << 30; int n, m;struct edge {int from;int to;int w; }; vector<edge>e[N];struct node {int id;int dis;friend bool operator<(const node &a, const node &b) {return a.dis > b.dis;} };void dijkstra(int s) //s為起點(diǎn) {priority_queue<node>q;memset(done, 0, sizeof(done));for (int i = 1; i <= n; i++)dis[i] = INF;memset(done, 0, sizeof(done));dis[s] = 0;q.push({s, dis[s]});while (q.size()) {node t = q.top();q.pop();if (done[t.id])continue;done[t.id] = true;for (int i = 0; i < e[t.id].size(); i++) {edge y = e[t.id][i];if (done[y.to])continue;if (dis[y.to] > y.w + t.dis) {dis[y.to] = y.w + t.dis;q.push({y.to, dis[y.to]});}}} }int main() {while (cin >> n >> m, n, m) {for (int i = 1; i <= n; i++)e[i].clear();while (m--) {int a, b, c;cin >> a >> b >> c;e[a].push_back({a, b, c});e[b].push_back({b, a, c});}int start;cin >> start;//起點(diǎn)dijkstra(start);int no;while (cin >> no, no)//詢問no點(diǎn)到起點(diǎn)的距離{cout << dis[no] << endl;}}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的C++实现dijkstra单源最短路径算法-邻接表+优先队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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