halisi7

一个专注技术的组织

0%

图的最短路径-c语言

发表于 更新于 分类于 阅读次数： Valine：
Floyd-Warshall算法、Dijkstra 算法与Bellman-Ford算法

最短路径

只有五行的算法——Floyd-Warshall

image-20220420161223170

image-20220420161309239

分析

image-20220420161515897

image-20220420161546585

image-20220420161644437

image-20220420161659570

image-20220420161715981

image-20220420161735392

image-20220420161756947

代码实现（Floyd-Warshall）

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
#include <stdio.h>
int main() { //解决多源最短路径
	int e[51][51] ;
	int i, j,a,b, k,c,n,m;
	int inf = 9999999;
	
	scanf_s("%d %d", &n, &m);
	for(i=1;i<=n;i++)
		for (j = 1; j <= n; j++) {
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] = inf;
		}
	for (i = 1; i <= m; i++) {
		scanf_s("%d %d %d", &a, &b,&c);
		e[a][b] = c;
	}
		for(k=1;k<=n;k++)
			for(i=1;i<=n;i++)
				for (j = 1; j <= n; j++) {
					if (e[i][j] > e[i][k] + e[k][j])
						e[i][j] = e[i][k] + e[k][j];
				}
		for (i = 1; i <= n; i++) {
			for (j = 1; j <= n; j++) {
				printf("%10d", e[i][j]);
			}
			printf("\n");
		}
		getchar(); getchar();
		return 0;
}

注意：

image-20220420162127182

image-20220420162150024

输入

1
2
3
4
5
6
7
8
9
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12

输出

1
2
3
4
0         2         5         4
9         0         3         4
6         8         0         1
5         7        10         0

总结

时间复杂度O(N^3^)。

image-20220420162337450

image-20220420162403850

Dijkstra 算法——通过边实现松弛

image-20220420162603014

image-20220420162629272

image-20220420162643445

image-20220420162706159

image-20220420162722163

image-20220420162740290

代码实现

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
#include <stdio.h>
int main() {
	int e[51][51] ;
	int i, j, n, m,a,b,c,min,u,inf=999999;
	int book[51] = {0};
	int dis[51];
	scanf_s("%d %d", &n, &m);
	for(i=1;i<=n;i++)//二维数组初始化
		for (j = 1; j <= n; j++) {
			if (i == j)e[i][j] = 0;
			else
			{
				e[i][j] = inf;
			}
		}
	for (i = 1; i <= m; i++) {//读入
		scanf_s("%d %d %d", &a, &b,&c);
		e[a][b] = c;
	}
	//初始化dis数组，1号到各个顶点的初始路程
	for (i = 1; i <= n; i++)
		dis[i] = e[1][i];
	book[1] = 1;
	//Dijkstra算法核心
	for (i = 1; i <= n-1; i++) {//需要重复n-1次
		//找到离1号顶点最近的点
		min = inf;
		for (j = 1; j <= n ; j++) {
			if (book[j]==0&&dis[j] < min) {
				min = dis[j];
				u = j;
			}
		}
		book[u] = 1;
		for (j = 1; j <= n ; j++) {
			if (e[u][j] < inf) {
				if (dis[j] > e[u][j] + dis[u]) {
					dis[j] = e[u][j] + dis[u];
				}
			}
		}
	}
	for (i = 1; i <= n; i++) {
		printf("%d ", dis[i]);
	}
	return 0;
}

输入

1
2
3
4
5
6
7
8
9
10
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4

输出

1
0 1 8 4 13 17

总结

时间复杂度O(N^2^)

Dijkstra算法 是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，
若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，
就需要使用其他的算法来求解最短路径， Bellman-Ford算法就是其中最常用的一个。

Bellman-Ford一解决负权边

用邻接表表示法存储图

image-20220420163559715

image-20220420163616022

image-20220420163639371

image-20220420163701983

image-20220420163730580

image-20220420163951199

image-20220420163920967

image-20220420164025663

image-20220420164044353

image-20220420164105199

image-20220420164121860

image-20220420164144654

image-20220420164230479

代码实现

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
64
65
66
67
#include <stdio.h>
int main() {
	int dis[51],bak[51] , u[51], v[51], w[51], first[50], next[51];
	int n, m, i, j ,check,flog; 
	int inf = 999999;
	scanf_s("%d %d", &n, &m);
	
	
	for (i = 1; i <= m; i++) {
		scanf_s("%d %d %d", &u[i], &v[i], &w[i]);
		
	}
	for (i = 1; i <= n; i++) {
		dis[i] = inf;
		//printf("%d ", dis[i]);
	}
	dis[1] = 0;
	
	//最多进行n-1轮更新，但不一定就要循环n-1轮，因为可能未到n-1轮就已经计算出了最短路径
	for (i = 1; i <= n - 1; i++) {
		
		//对数组进行复制
		for (j = 1; j <= m; j++) {
			bak[i] = dis[i];
		}
		check = 0;//用于标记数组是否更新
		//如果到v[j]顶点距离大于从u[j]顶点出发+w[i](路程)的话，就对dis[]数组的v[j]路程进行更新
		for (j = 1; j <= m; j++) {

			if (dis[v[j]] > dis[u[j]] + w[j]) {
				dis[v[j]] = dis[u[j]] + w[j];
				
			}
		}
		for (j = 1; j <= m; j++) {//检查数组是否有更新
			if (bak[i] != dis[i]) {//如果没有更新标记为未更新并结束
				check = 1;
				break;
			}
		}
		if (check = 1) {//如果没有更新了，就退出循环
			break;
		}
	}
	flog = 0;//用于标记是否有负权回路
	for (j = 1; j <= m; j++) {
		if (dis[v[i]] > dis[u[i]] + w[i]) {//如果有负权回路
			flog = 1;
			
			break;
		}
	}
	//输出
	if (flog == 1) {
		printf("有负权回路。");
	}
	else {
	for (i = 1; i <= n; i++) {
		printf("%d ", dis[i]);
		}
	}

	
	getchar(); getchar();
	return 0;
	
}

输入

1
2
3
4
5
6
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3

输出

1
有负权回路。

image-20220420164810012

image-20220420164850256

Bellman-Ford的队列优化

image-20220420172948963

image-20220420173049942

image-20220420173102361

image-20220420173124210

image-20220420173437603

代码实现

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
#include <stdio.h>

int main() {
	int n, m, i,k;
	int dis[6] = { 0 }, book[6] = { 0 };
	int u[8], v[8], w[8];
	int first[6] ;
	int next[8];
	int que[101] = { 0 }, tail = 1, head = 1;
	int inf = 999999;
	scanf_s("%d %d", &n, &m);
	for (i = 1; i <= n; i++)first[i] = -1;

	for (i = 1; i <= m; i++) {
		scanf_s("%d %d %d", &u[i], &v[i], &w[i]);
		next[i] = first[u[i]];
		first[u[i]] = i;
	}
	for (i = 1; i <= n; i++)
		dis[i] = inf;
	dis[1] = 0;
	
	for (i = 1; i <= n; i++)book[i] = 0;
	
	que[tail] = 1;
	book[1] = 1;
	tail++;
	while (head < tail) {
		k = first[que[head]];
		while (k != -1) {
			
			if (dis[v[k]] > dis[u[k]] + w[k]) {
				dis[v[k]] = dis[u[k]] + w[k];


				if (book[v[k]] == 0) {
					que[tail] = v[k];
					
					tail++;
					book[v[k]] = 1;
				}
			}
			k = next[k];
			
		}
		book[que[head]] = 0;
		head++;
	}
	for (i = 1; i <= n; i++)
		printf("%d ", dis[i]);
	getchar(); getchar();
	return 0;

}

输入

1
2
3
4
5
6
7
8
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6

输出

1
0 2 5 9 9

总结

image-20220420173859784

image-20220420173913376

image-20220420173930250

打赏一下作者~ ฅ( ̳• ◡ • ̳)ฅ