最短的求解一般会遇到多种情况

  • 有向无环图
    • 权值为正
    • 权值有负
  • 有向有环图
    • 权值为正
    • 权值有负

负权边和负权环 Bellmon-Ford

权值非负的有向或无向图 Dijkstra

Dijkstra

Dijkstra本质上是一种贪心算法，通过不断调整每个点的“当前距离”最终得到最优结果

这种不断调整的过程，维基百科上面称为**“relax"（松弛）**

算法流程

对于求一点s到其他所有点的最短距离

对于每个点v均维护一个当前距离（dis[v]）和 是否访问过（vis[v]）。首先将dis[s]初始化为无穷，所有点访问状态(vis)置为未访问

对于一条边u->v，其边权为weight[u->v]，我们存储在了v.first中(v为G[u]中的一个邻接点)

  1. 从所有未访问的点中，找出当前距离最小的，设为u，并将其标记为已访问的。

  2. 调整u的所有边（若是有向图则为出边）连接的并且未被访问过的点：

    若weight[u->v] + dis[u] < dis[v], 则将dis[v]更新为dis[u]+weight[u->v]，体现在代码中的操作即是：if (dis[v.second] > dis[x] + v.first)

  3. 重复1和2步骤，直到所有点都被标记为已访问的，则dis[i]即s到i的最短距离

    （当然，如果只想求从s到某一点的最短距离，那么当该点被标记为访问过之后可直接退出）

  4. 如果还想得出两点间的最短路径，可以通过一个pre数组，在步骤2的**if (dis[v.second] > dis[x] + v.first)**后添加操作：pre[v] = u

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
vector < pair<int, int> > G[MAXN];
int dis[MAXN];
bool vis[MAXN];
int n, m, s;

#define PII pair<int, int> 
priority_queue < PII, vector<PII>, greater<PII>> q;//小根堆，堆顶存放可访问的 未访问节点中 距离最小的节点

inline void dijkstra() {
    for (int i = 1; i <= n; ++i)dis[i] = 0x7fffffff;
    dis[s] = 0;
    q.push({ 0, s });

    while (!q.empty()) {
        int u = q.top().second;//由于点的维护依靠的是小根堆，堆顶的元素即是《未访问节点中 距离最小的节点》
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        
        for (auto& v : G[u]) {//邻接点访问
            if (dis[v.second] > dis[u] + v.first) {
                dis[v.second] = dis[u] + v.first;
                if (!vis[v.second]) {
                    q.push({ dis[v.second], v.second });//当前更新节点未完成更新(未被标记)，将当前节点和当前节点长度入队
                }
            }
        }

    }
}


/////////MAIN/////////
cin >> n >> m >> s;
//register关键字表示使用cpu内部寄存器，这将加快变量的读写速度
for (register int i = 0; i < m; ++i){
    register int u, v, w;
    cin >> u >> v >> w;
    G[u].push_back({ w,v });//有向图
}

Bellmon

bellmon-ford是一种单源最短路算法，时间复杂度是$O(VE)$ ,显然不如dijkstra快，但它可以处理负权边和负权环的情况。它基于一个很基本的事实：

对于一个不包含负权环的V个点的图，任意两点之间的最短路径至多包含V-1条边

如果存在负权环，每次在负权环上走一圈都会使环上的每一个点的距离减少，因此不存在最短路径。

bellmon-ford算法可以检测出这种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define MAXN 1501
#define MAXE 50001
#define inf 99999999

//	u		   v		w
int from[MAXE], to[MAXE], weight[MAXE];
//dis为原点到当前节点的最短路径 pre存储最短路径的前后关系
int dis[MAXN], pre[MAXN];

void bellmon() {
	for (int i = 0; i < n; i++)dis[i] = inf;//初始化距离为极大值
	dis[1] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int u = from[j], v = to[j], w = weight[j];
			if(dis[u] + w < dis[v]) {
                //《松弛》操作，如果u到v有一条边，dis[v]存储u到v的最短边
				dis[v] = dis[u] + w;
                //pre表示最短路径上v的前一个节点是u
				pre[v] = u;
			}
		}
	}
    
    /*
    bellmon-ford算法可以判断负权环的存在：
    	只需在算法的最后对每条边再松弛一次
    	如果发现有点的距离得到更新
    	说明存在负权环
    			"因为没有负权环时最短路径的长度至多为V-1"
    */
}

SPFA

spfa (shortest path faster algorithm)是对Bellmon的一个改进

spfa 采用类似bfs的思想，使用一个队列，只松弛那些可能更新点的距离的边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define MAXN 1501
#define inf 99999999

vector < pair<int, int > > G[MAXN];
//dis为原点到当前节点的最短路径
int dis[MAXN];
bool inq[MAXN];
///////////
int n, m;//
///////////
void spfa() {
	for (int i = 0; i < n; i++)dis[i] = inf;//初始化距离为极大值
	dis[1] = 0;
	queue<int> q;
	q.push(1); inq[1] = true;

	while (q.size()) {
		int u = q.front(); q.pop();
		inq[u] = false;
		for (auto& v : G[u]) {
			if (dis[v.first] > dis[u] + v.second) {
				dis[v.first] = dis[u] + v.second;
				if (!inq[v.first]) {
					q.push(v.first);
					inq[v.first] = true;
				}
			}
		}
	}

}


//main
cin >> n >> m;
int u, v, w;
for (int i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    G[u].push_back({ v,-w });//-w 求最长路
}