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
Dijkstra-朴素 O(n2)
1.初始化距离数组, dist[1] = 0, dist[i] = inf;
2.for n次循环 每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离
3.将不在S中dist_min的点->t
4.t->S加入最短路集合
5.用t更新到其他点的距离

Dijkstra-堆优化 O(mlogm)
1.利用邻接表，优先队列
2.在priority_queue<PII,vector<PII>,greater<PII>> heap;中将返回堆顶
3.利用堆顶来更新其他点，并加入堆中类似宽搜

Bellman_ford O(nm)
1.注意连锁想象需要备份, struct Edge{int a,b,c} Edge[M];
2.初始化dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
3.松弛k次，每次访问m条边

Spfa O(n)∼O(nm)
1.利用队列优化仅加入修改过的地方
2.for k次
3.for 所有边利用宽搜模型去优化bellman_ford算法
更新队列中当前点的所有出边

Floyd O(n3)
1.初始化d
2.k, i, j 去更新d

单源最短路

点击查看

所有边权都是正数

朴素的Dijkstra算法

点击查看

1.时间复杂度O(n^2) n为点的数量

所以与堆优化版进行对比，如果边的数量m与n^2是一个级别，那就是稠密图，建议使用朴素dijkstra算法， 同时稠密图用邻接矩阵来存

2.算法实现

1
2
3
4
5
6
7
8
9
s[]:存储所有已经确定最短距离的点

①dist[1] = 0, dist[i] = ∞;

②for i : 1~n{
	t <--不在s中的距离最近的点
	s <--t
	用t更新其他点的距离：s <-- t + t <-- x 的距离是否大于 s <-- x 的距离，如果大于，那就更新s <-- x
}每次迭代都可以确定一个点到起点的最短路

例题:

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
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
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
42
43
44
45
46
47
48
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];//邻接矩阵 
int dist[N];//表示从一号点走到每个点当前的最短距离是多少， 
bool st[N];//表示每个点的最短距离是否确定

int dijkstra(){
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	for(int i = 0; i < n; ++i){
		int t = -1;
		for(int j = 1; j <= n; ++j){
			if(!st[j] && (t == -1 || dist[t] > dist[j]))//这个循环的意思是在所有st[j] == false(也就是说所有没有确定最短距离的点钟)
				t = j;                                  //找到dist最小的点，原因即dijkstra算法的原理
		}
		st[t] = true;
		for(int j = 1; j <= n; ++j)
			dist[j] = min(dist[j], dist[t] + g[t][j]); //用t来更新其他点的距离
	}
	if(dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

int main(){
	scanf("%d%d", &n, &m);
	
	memset(g, 0x3f, sizeof g);
	
	while(m--){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = min(g[a][b], c);//重边的话，保留最短的边即可 
	}
	
	cout << dijkstra() << endl;
	
	return 0;
}


堆优化版的Dijkstra算法

点击查看

1.时间复杂度O(mlogn) m为边的数量

与朴素算法对比，如果是稀疏图，也就是边的数量m与n是一个级别，建议使用堆优化版的dijkstra算法， 同时稀疏图用邻接表来存

2.算法实现

1
2
3
4
5
6
7
8
9
s[]:存储所有已经确定最短距离的点

①dist[1] = 0, dist[i] = ∞;

②for i : 1~n{
	t <--将不在s中的距离最近的点赋给t(这一步可以用堆结构来优化,用优先队列就行)
	s <--t
	用t更新其他点的距离：s <-- t + t <-- x 的距离是否大于 s <-- x 的距离，如果大于，那就更新s <-- x
}每次迭代都可以确定一个点到起点的最短路

例题：

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
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 2e5 + 10;

int h[N], e[N], ne[N], idx;
int w[N];//记录每条边的权重，也就是距离 
int dist[N];
bool st[N];
int n, m;

void add(int a, int b, int c){
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int dijkstra(){
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	
	heap.push({0, 1});
	
	while(heap.size()){
		auto t = heap.top();
		heap.pop();
		
		int ver = t.second, distance = t.first;
		if(st[ver]) continue;
		st[ver] = true;
		
		for(int i = h[ver]; i != -1; i = ne[i]){
			int j = e[i];
			if(dist[j] > distance + w[i]){
				dist[j] = distance + w[i];
				heap.push({dist[j], j});
			}
		}
	}
	if(dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

int main(){
	scanf("%d%d", &n, &m);
	
	memset(h, -1, sizeof h);
	
	while(m--){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	
	cout << dijkstra() << endl;
	
	return 0;
}

存在负权边

Bellman-Ford算法

点击查看

1.时间复杂度 O(mn) 也就是点数乘边数

2.基本思路

1
2
3
4
5
6
for(n次){
	要备份dist数组
	每次for循环所有边a, b, w{
	更新dist[b] = min(dist[b], dist[a] + w);
	}
}

3.bellman-fold算法迭代的次数有实际意义
迭代k次求得的dist数组的含义是从一号点经过不超过k条边走到每个点的最短距离，所以当题目要求对经过的边数有限制的时候，要用bellman-fold算法
4.bellman-fold算法可以用来求是否存在负环

例题：

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
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。

输入样例：
3 3 1
1 2 1
2 3 1
1 3 3
输出样例：
3
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
42
43
44
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 1e5 + 10;

int dist[N], backup[N];
int n, m, k;

struct Edge{
	int a, b, w;
}edges[M];

int bellman_ford(){
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	
	for(int i = 0; i < k; ++i){
		memcpy(backup, dist, sizeof dist);
		for(int j = 0; j < m; ++j){
			int a = edges[j].a, b = edges[j].b, w = edges[j].w;
			dist[b] = min(dist[b], backup[a] + w);
		}
	}
	if(dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
	else return dist[n];
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	
	for(int i = 0; i < m; ++i){
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = {a, b, w};
	}
	
	int t = bellman_ford();
	if(t == 0x3f3f3f3f) puts("impossible");
	else printf("%d", t);
	
	return 0;
}

SPFA算法(是Bellman-Ford的优化）

点击查看

1.时间复杂度 一般情况：O(m) 最坏：O(nm)

2.尽管是BF算法的优化，但是不是所有情况都可以使用SPFA算法

如果对经过的边数进行限制，那就只能使用Bellman-Ford算法

99%的情况都可以用spfa（不能有负环）

3.基本思路

1
2
3
4
5
6
7
8
9
主要思路：只用更新过的点来更新其他点
用宽搜来做优化
①把起点放到queue中
while(queue不空){队列中存的是所有变小了的结点，更新过了的点
	①t<-q.front;
	q.pop();
	②更新t的所有出边b
	queue<-b
}

例题1：spfa求最短路

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
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx, w[N];
int n, m;
int dist[N];
bool st[N];//用来记录点是否在queue中

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while(q.size()){
       	int t = q.front();
        q.pop();
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if(!st[j]){
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    int t = spfa();
    
    if(t == 0x3f3f3f3f) puts("impossible");
    else printf("%d", t);
    
    return 0;
}

例题2:spfa判断负环

原理：dist[x]数组的含义是当前从一号点到x点最短路径的长度，每次更新dist数组的同时更新cnt数组，表示当前最短路的边数，如果某一次cnt[x] >= n的话，由抽屉原理，经过了n条边，说明一共经过了n + 1个点，说明有点不止经过了一次，说明存在环，并且是负权环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围
1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3
1 2 -1
2 3 4
3 1 -4
输出样例：
Yes
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 10010;
int h[N], e[N], ne[N], idx, w[N];
int n, m;
bool st[N];
int cnt[N], dist[N];//cnt数组存的是当前最短路的边数

void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa(){
    queue<int> q;
    for(int i = 1; i <= n; ++i){
        st[i] = true;
        q.push(i);
    }
    
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;
                if(!st[j]){
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    if(spfa()) puts("Yes");
    else puts("No");
    
    return 0;
}

多源汇最短路

点击查看

Floyd算法

点击查看

1.时间复杂度 O(n^3)

2.基本思路：

1
2
3
4
5
6
7
8
9
10
11
d[i,j]邻接矩阵存储所有的边,然后三重循环
for(k : 1~n){
	for(i : 1~n){
		for(j : 1~n){
			d[i,j] = min(d[i,j], d[i,k] + d[k,j]);
		}
	}
}

d[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么d[i, j, k] = min(d[i, j, k - 1), d[i, k, k - 1] + d[k, j, k - 1]。
因此在计算第k层的d[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。

例题：

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
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式
第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。

输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1
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
42
43
#include <cstring>
#include <iostream>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int d[N][N];
int n, m, k;

void floyd(){
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
            
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }
    
    floyd();
    
    while(k--){
        int a, b;
        scanf("%d%d", &a, &b);
        
        if(d[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", d[a][b]);
    }
    
    return 0;
}