【笔记】基于链式前向星的图论算法（二）最短路

图论

Life in OI

Publish Date: 2019-09-13

Word Count: 1.6k

Read Times: 7 Min

Part 1 单源最短路（SSSP）

Dijkstra

Dijkstra只能用于无负权边的图。

设图$G=(V,E)$所有顶点的集合为$V$，起点为$s$,最短路径树中包含的顶点集合为$S$。

在各计算步骤中，我们将选岀最短路径树的边和顶点并将其添加至$S$。

对于各顶点$i$，设仅经由$S$内顶点的$s$到$i$的最短路径成本为$d[i]$，$i$在最短路径树中的父结点为$p[i]$。

初始状态下将$S$置空。

初始化$S$的$d[s] = 0$；除s以外，所有属于V的顶点i的$d[i]=\infty$
循环进行下述处理，直至$S=F$为止。
- 从$V-S$中选岀$d[u]$最小的顶点$u$
- 将$u$添加$S$至，同时将与$u$相邻且属于$V-S$的所有顶点$v$的值按下述方式更新：

if d[u] + w(u, v) < d[v]
    d[v] = d[u] + w(u, v)
    p[v] = u

伪代码：

dijkstra(s)
    将所有顶点u的color[u]设为WHITE，d[u]初始化为INFTY
    d[s] = 0
    p[s] = -1

    while true
        mincost = INFTY
        for i从0至n-1
            if color[i] != BLACK && d[i] < mincost
                mincost = d[i]
                u = i

        if mincost == INFTY
            break

        color[u] = BLACK

        for v从0至n-1
            if color[v] != BLACK且u和v之间存在边
                if d[u] + M[u][v] < d[v]
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[v] = GRAY

邻接矩阵实现的Dijkstra算法复杂度为$O(|V|^2)$。使用邻接表时，更新最短距离只需访问每条边一次，因此更新最短距离复杂度为$O(|E|)$。
但是要枚举所有顶点来查找下一个使用的顶点，因此最终复杂度还是$O(|V|^2)$。

Dijkstra堆优化

把每个顶点当前的最短距离用堆维护，可以省去松弛和查找操作，直接把节点和数据丢进优先队列。

更新最短距离时，每次从堆中取出的最小值就是下一次要使用的顶点。

在使用堆优化时，加入堆的应为当前将要被更新的点的编号和当前距离；而当距离被更新时，应新加入一个包含当前点的编号和当前距离的节点。

在单源最短路的题目中，Dijkstra是最好用的算法。

/*
 * @Author: thyzzs
 * @Date: 2019-11-06 19:00:52
 * @LastEditTime: 2024-03-11 20:38:18
 * @Description: Dijkstra
 */
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <climits>
#define MAX_V 100005

using namespace std;
// typedef pair<int,int> P;
struct edge {
	int to, cost;
};

int V, E, S;
int u, v, w;
edge e;
vector<edge> G[MAX_V];
int d[MAX_V], vis[MAX_V];

void dijkstra(int s) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
	fill(d, d + V, INT_MAX);
	d[s] = 0;
	que.push(make_pair(0, s));
	
	while (!que.empty()) {
		pair<int, int> p = que.top();
		que.pop();
		int t = p.second;
		if (vis[t])
			continue;
		vis[t] = 1;
		for (int i = 0; i < G[t].size(); i++) {
			e = G[t][i];
			if (d[e.to] > d[t] + e.cost) {
				d[e.to] = d[t] + e.cost;
				if (!vis[e.to])
					que.push(make_pair(d[e.to], e.to));
			}
		}
	}
	return;
}

int main() {
	scanf("%d%d%d", &V, &E, &S);
	S--;
	for (int i = 1; i <= E; i++) {
		scanf("%d%d%d", &u, &v, &w);
		u--;
		v--;
		e.to = v;
		e.cost = w;
		G[u].push_back(e);
		//e.to = u;
		//G[v].push_back(e);
	}
	dijkstra(S);
	for (int i = 0; i < V; i++) {
		printf("%d ", d[i]);
	}
	puts("");
	return 0;
}

Bellman-Ford

Bellman-Ford算法基于动态规划的思想，即反复用已有的边来更新最短距离。即如果$d[u] + cost(u, v) < d[v]$则更新d[v]。

因为最短路经过的边数量不超过n − 1，所以至多n − 1次更新后d[x]即为源点S到地图上其余每个点的最短距离。

d[S] = 0，其余d[x] = INF
对于每条边$(u, v)$，如果$d[u] < INF$且$d[u] + cost(u, v) < d[v]$，则$d[v] = d[u] + cost(u, v) < d[v]$
循环上一步至多n − 1次
对于每条边$(u, v)$，如果$d[u] < INF$且$d[u] + cost(u, v) < d[v]$，则图中存在负权回路

总时间复杂度$O(nm)$

/*
 * @Author: thyzzs
 * @Date: 2019-11-06 19:00:52
 * @LastEditTime: 2024-03-11 20:38:18
 * @Description: Bellman-Ford
 */
#include <cstdio>
#include <iostream>
#include <climits>

#define MAX_E 500005
#define MAX_V 10005

using namespace std;

struct edge {
	int from, to, cost;
};

edge es[MAX_E];

int d[MAX_V];
int V, E, S;

void Bellman_Ford(int s) {
	for (int i = 1; i <= V; i++)
		d[i] = INT_MAX;
	d[s] = 0;
	while (true) {
		bool update = false;
		for (int i = 1; i <= E; i++) {
			edge e = es[i];
			if (d[e.from] != INT_MAX && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if (!update)
			break;
	}
}

int main() {
	scanf("%d%d%d", &V, &E, &S);
	for (int i = 1; i <= E; i++) {
		scanf("%d%d%d", &es[i].from, &es[i].to, &es[i].cost);
	}
	Bellman_Ford(S);
	for (int i = 1; i <= V; i++) {
		printf("%d ", d[i]);
	}
	puts("");
	return 0;
}