C++實作dijkstra單源最短路徑算法-鄰接表+優先隊列

dijkstra單源最短路徑算法不允許邊權值為負，适用的圖範圍可以很大。

代碼如下：

#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為起點
{
	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;//起點
		dijkstra(start);
		int no;
		while (cin >> no, no)//詢問no點到起點的距離
		 {
			cout << dis[no] << endl;
		}
	}
	return 0;
}