最短路 - Dijkstra 算法

Dijkstra(迪杰斯特拉)算法是基于贪心思想的单源最短路算法

暴力 Dijkstra

具体如下：

struct node { int v, w; };
vector<node> e[N];
int dist[N], vis[N];

e[u] 存的是节点 u 的所有出边的终点和边权，dist[u] 存 u 到原点 s 的最小距离， vis[u] 标记是否走过

void dijkstra(int s) {
	memset(dist, 0x3f, sizeof dist);  // 初始先让所有点设为 +∞
	dist[s] = 0;  // 原点离自身距离为0
	for(int i = 1; i < n; i ++) {  // 枚举次数
		int u = 0;
		for(int j = 1; j <= n; j ++) {  // 枚举点
			if(!vis[j] && dist[j] < dist[u]) u = j;  // 选择一个距离最小的标记
		}
		vis[u] = 1;
		for(auto ed : e[u]) {  // 对u的所有出边，更新邻边v的最小距离
			int v = ed.v, w = ed.w;
			if(dist[v] > dist[u] + w) dist[v] = dist[u] + w;
		}
	}
}

主函数：

int main() {
	cin >> n >> m >> s;
	for(int i = 0; i < m; i ++) {
		cin >> a >> b >> c;
		e[a].push_back({b, c});  // 加入a的邻边b和权值c
	}
	dijkstra(s);
	return 0;
}

但是以上的方法对于负边权不适用，会出错；

并且时间复杂度为 \(O(n^2 + m) ≈ O(n^2)\)

对于 \(n = 10^3, m = 10^6\) AC, 而对于 \(n = 10^6, m = 10^6\) 则 TLE;

Dijkstra 算法的堆优化 ---- 用优先队列维护被更新的点的集合

Heap - Dijkstra

具体如下：

priority_queue<pair<int, int>> q;

创建一个pair类型的大根堆 q{-距离， 点}，或者是 小根堆 q{距离， 点}; 但小根堆需要自己用结构体加重载运算符

小根堆写法：

struct node
{
    int first;  // 距离
    int second;  // 点编号
    bool operator <(const node &x)const  // 重载运算符
    {
        return x.first<first;
    }
};

priority_queue<node> q;

void dijkstra(int s) {
	memset(dist, 0x3f, sizeof dist);
	dist[s] = 0;
	q.push({0, s});  // 原点入队
	while(q.size()) {
		auto t = q.top();
		q.pop();
		int u = t.first;  // 从队头弹出距离最小的点u
		if(vis[u]) continue;  //如果走过就直接出队
		vis[u] = 1;  //没走过标记下
		for(auto ed : e[u]) {
			int v = ed.v, w = ed.w;
			if(dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				q.push({-dist[v], v});  // 把更小的点及距离入队
			}
		}
	}
}

总结：