图-弗洛伊德（FloydWarshall）算法详解（含全部代码）_弗洛伊德算法代码(1)_弗洛伊德warshall

先自我介绍一下，小编浙江大学毕业，去过华为、字节跳动等大厂，目前阿里P7

深知大多数程序员，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新网络安全全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上网络安全知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

如果你需要这些资料，可以添加V获取：vip204888 （备注网络安全）

正文

• Adjancent(Graph G,VexType v,VexType w) 判断是否存在弧(v,w)函数 参数：图G，某弧两端点v和w 作用：判断是否存在弧(v,w)
• BFS(Graph G, int start) 广度遍历函数 参数：图G,开始结点下标start 作用：宽度遍历
• DFS(Graph G, int start) 深度遍历函数（递归形式）参数：图G,开始结点下标start 作用：深度遍历
• Dijkstra(Graph G, int v)  最短路径 - Dijkstra算法 参数：图G、源点v
• Bellman_Ford(Graph G, int v)  最短路径 - Bellman_Ford算法  参数：图G、源点v 作用：计算不含负圈图的最短路径 返回是否有圈
• Floyd_Wallshall(Graph G)    最短路径 - Floyd_Wallshall算法  参数：图G 作用：计算不含负圈图的最短路径 返回是否有圈

功能实现函数

• CreateGraph(Graph &G) 创建图功能实现函数 参数：图G  InsertNode 作用：创建图
• BFSTraverse(Graph G)  广度遍历功能实现函数 参数：图G 作用：宽度遍历
• DFSTraverse(Graph G)  深度遍历功能实现函数 参数：图G 作用：深度遍历
• Shortest_Dijkstra(Graph &G) 调用最短路径-Dijkstra算法 参数：图G、源点v
• Shortest_Bellman_Ford(Graph &G) 调用最短路径- - Bellman_Ford算法  参数：图G
• Shortest_Floyd_Wallshall(Graph &G) 调用最短路径- - Floyd_Wallshall算法  参数：图G

测试使用图

测试使用图

算法讲解

初始化

表格行为i,列为j。D及P后小括号内的值为迭代次数。

D矩阵主对角线为0，其余与邻接矩阵相同。

P矩阵存-1，在输出最短路径时作为递归出口。

迭代

D矩阵的状态转移方程：D(m)[i][j]=min{D(m-1)[i][j],D(m-1)[i][k]+D[k][j]},0<<k<<n-1,其中,m为迭代次数，n为节点个数。

思路：添加一个点Vk,找到Vk的入弧Vi->Vk，再找到Vk的出弧,Vk->Vj，比较D[i][j]与D[i][k]+D[k][j]的大小。

若D矩阵有更新，则对应P矩阵的值为更新处最短路径第一条弧的终点。

D(1)

P(1)

D(2)

加入点V0，V0的入弧有V1->V0与V3->V0，出弧有V0->V1与V0->V2。

经比较D(1)[3][2]>D(1)[3][0]+D(1)[0][2]，6>5-3=2，所以，将6更新为2。

P(2)

P(2)[3][2]由P(1)[3][2]改为0，因为最短路径为V3->V0->V2，第一条弧的终点为V0。

D(3)

加入点V1，V1入弧有V0->V1，V2->V1以及V3->V1，出弧有V1->V2,V1->V0。

经比较,D(2)[2][0]>D(2)[2][1]+D(2)[1][0]，∞>10-3=7，所以，将∞更新为7。

D(2)[3][0]>D(1)[3][1]+D(2)[1][0]，5>6-3=3，所以，将5更新为3。

D(2)[3][2]>D(1)[3][1]+D(2)[1][2]，2>6-7=-1，所以，将2更新为-1。

P(3)

P(3)[2][0]改为1，因为最短路径为V2->V1->V0，第一条弧的终点为V1。

P(3)[3][0]改为1，因为最短路径为V3->V1->V0，第一条弧的终点为V1。

P(3)[3][2]改为1，因为最短路径为V3->V1->V2，第一条弧的终点为V1。

下面的由读者根据原理及矩阵自己补充，加深印象。

D(4)

P(4)

D(5)

P(5)

注意：弗洛伊德算法的最短路径在输出时不是倒着的，我们记录的是第一条弧的终点。例如，p[2][0]=3，P[3][0]=1,P[1][0]=-1，

则V[2]到V[0]的最短路径为2->3->1->0，值为6。也就是看P矩阵的列，这是与前面两篇最短路径算法不同的地方，需注意。

弗洛伊德算法代码

//最短路径 - Floyd_Wallshall算法  参数：图G 作用：计算不含负圈图的最短路径 返回是否有圈
bool Floyd_Wallshall(Graph G)
{
	//初始化
	for (int i = 0; i<G.vexnum; i++)
		for (int j = 0; j < G.vexnum; j++)
		{
			if (i == j)F_D[i][j] = 0;
			else F_D[i][j] = G.Edge[i][j];
			P[i][j] = -1;
		}
	//初始化结束，开始迭代
	for(int k=0;k<G.vexnum;k++)
		for (int i = 0; i<G.vexnum; i++)
			for (int j = 0; j<G.vexnum; j++)
				if (F_D[i][j] > F_D[i][k] + F_D[k][j])
				{
					F_D[i][j] = F_D[i][k] + F_D[k][j];
					P[i][j] = k;
				}
	bool flag = true;
	for (int i = 0; i < G.vexnum; i++)
		for (int j = 0; j < G.vexnum; j++)
			if (i==j&&F_D[i][j] < 0)
			{
				flag = false;
				break;
			}
	return flag;
}
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

全部代码

/*
Project: 图-最短路径-Bellman-Ford算法（可含有负权弧）
Date:    2019/10/24
Author:  Frank Yu
基本操作函数:
InitGraph(Graph &G)             初始化函数 参数：图G 作用：初始化图的顶点表，邻接矩阵等
InsertNode(Graph &G,VexType v) 插入点函数 参数：图G,顶点v 作用：在图G中插入顶点v,即改变顶点表
InsertEdge(Graph &G,VexType v,VexType w) 插入弧函数 参数：图G,某弧两端点v和w 作用：在图G两点v,w之间加入弧，即改变邻接矩阵
Adjancent(Graph G,VexType v,VexType w) 判断是否存在弧(v,w)函数 参数：图G，某弧两端点v和w 作用：判断是否存在弧(v,w)
BFS(Graph G, int start) 广度遍历函数 参数：图G,开始结点下标start 作用：宽度遍历
DFS(Graph G, int start) 深度遍历函数（递归形式）参数：图G,开始结点下标start 作用：深度遍历
Dijkstra(Graph G, int v)  最短路径 - Dijkstra算法 参数：图G、源点v
Bellman_Ford(Graph G, int v)  最短路径 - Bellman_Ford算法  参数：图G、源点v 作用：计算不含负圈图的最短路径 返回是否有圈
Floyd_Wallshall(Graph G)    最短路径 - Floyd_Wallshall算法  参数：图G 作用：计算不含负圈图的最短路径 返回是否有圈
功能实现函数：
CreateGraph(Graph &G) 创建图功能实现函数 参数：图G  InsertNode 作用：创建图
BFSTraverse(Graph G)  广度遍历功能实现函数 参数：图G 作用：宽度遍历
DFSTraverse(Graph G)  深度遍历功能实现函数 参数：图G 作用：深度遍历
Shortest_Dijkstra(Graph &G) 调用最短路径-Dijkstra算法 参数：图G、源点v
Shortest_Bellman_Ford(Graph &G) 调用最短路径- - Bellman_Ford算法  参数：图G
Shortest_Floyd_Wallshall(Graph &G) 调用最短路径- - Floyd_Wallshall算法  参数：图G
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<map>
#include<iterator>
#include<algorithm>
#include<iostream>
#define MaxVerNum 100 //顶点最大数目值
#define VexType char //顶点数据类型
#define EdgeType int //弧数据类型,有向图时邻接矩阵不对称，有权值时表示权值，没有时1连0不连
#define INF 0x3f3f3f3f//作为最大值
using namespace std;
//图的数据结构
typedef struct Graph
{
	VexType Vex[MaxVerNum];//顶点表
	EdgeType Edge[MaxVerNum][MaxVerNum];//弧表
	int vexnum, arcnum;//顶点数、弧数
}Graph;
//迪杰斯特拉算法全局变量
bool S[MaxVerNum]; //顶点集
int D[MaxVerNum];  //到各个顶点的最短路径
int F_D[MaxVerNum][MaxVerNum];//Floyd的D矩阵 记录最短路径
int Pr[MaxVerNum]; //记录前驱
//*********************************************基本操作函数*****************************************//
//初始化函数 参数：图G 作用：初始化图的顶点表，邻接矩阵等
int P[MaxVerNum][MaxVerNum];//最短路径记录矩阵
void InitGraph(Graph &G)
{
	memset(G.Vex, '#', sizeof(G.Vex));//初始化顶点表
									  //初始化弧表
	for (int i = 0; i < MaxVerNum; i++)
		for (int j = 0; j < MaxVerNum; j++)
			G.Edge[i][j] = INF;
	G.arcnum = G.vexnum = 0;          //初始化顶点数、弧数
}
//插入点函数 参数：图G,顶点v 作用：在图G中插入顶点v,即改变顶点表
bool InsertNode(Graph &G, VexType v)
{
	if (G.vexnum < MaxVerNum)
	{
		G.Vex[G.vexnum++] = v;
		return true;
	}
	return false;
}
//插入弧函数 参数：图G,某弧两端点v和w 作用：在图G两点v,w之间加入弧，即改变邻接矩阵
bool InsertEdge(Graph &G, VexType v, VexType w, int weight)
{
	int p1, p2;//v,w两点下标
	p1 = p2 = -1;//初始化
	for (int i = 0; i<G.vexnum; i++)//寻找顶点下标
	{
		if (G.Vex[i] == v)p1 = i;
		if (G.Vex[i] == w)p2 = i;
	}
	if (-1 != p1&&-1 != p2)//两点均可在图中找到
	{
		G.Edge[p1][p2] = weight;//有向图邻接矩阵不对称
		G.arcnum++;
		return true;
	}
	return false;
}
//判断是否存在弧(v,w)函数 参数：图G，某弧两端点v和w 作用：判断是否存在弧(v,w) 
bool Adjancent(Graph G, VexType v, VexType w)
{
	int p1, p2;//v,w两点下标
	p1 = p2 = -1;//初始化
	for (int i = 0; i<G.vexnum; i++)//寻找顶点下标
	{
		if (G.Vex[i] == v)p1 = i;
		if (G.Vex[i] == w)p2 = i;
	}
	if (-1 != p1&&-1 != p2)//两点均可在图中找到
	{
		if (G.Edge[p1][p2] == 1)//存在弧
		{
			return true;
		}
		return false;
	}
	return false;
}
bool visited[MaxVerNum];//访问标记数组，用于遍历时的标记
//广度遍历函数 参数：图G,开始结点下标start 作用：宽度遍历
void BFS(Graph G, int start)
{
	queue<int> Q;//辅助队列
	cout << G.Vex[start];//访问结点
	visited[start] = true;
	Q.push(start);//入队
	while (!Q.empty())//队列非空
	{
		int v = Q.front();//得到队头元素
		Q.pop();//出队
		for (int j = 0; j<G.vexnum; j++)//邻接点
		{
			if (G.Edge[v][j] < INF && !visited[j])//是邻接点且未访问
			{
				cout << "->";
				cout << G.Vex[j];//访问结点
				visited[j] = true;
				Q.push(j);//入队
			}
		}
	}//while
	cout << endl;
}
//深度遍历函数（递归形式）参数：图G,开始结点下标start 作用：深度遍历
void DFS(Graph G, int start)
{
	cout << G.Vex[start];//访问
	visited[start] = true;
	for (int j = 0; j < G.vexnum; j++)
	{
		if (G.Edge[start][j] <INF && !visited[j])//是邻接点且未访问
		{
			cout << "->";
			DFS(G, j);//递归深度遍历
		}
	}
}
//最短路径 - Dijkstra算法 参数：图G、源点v3
void Dijkstra(Graph G, int v)
{
	//初始化
	int n = G.vexnum;//n为图的顶点个数
	for (int i = 0; i < n; i++)
	{
		S[i] = false;
		D[i] = G.Edge[v][i];
		if (D[i] < INF)Pr[i] = v; //v与i连接，v为前驱
		else Pr[i] = -1;
	}
	S[v] = true;
	D[v] = 0;
	//初始化结束,求最短路径，并加入S集
	for (int i = 1; i < n; i++)
	{
		int min = INF;
		int temp;
		for (int w = 0; w < n; w++)
			if (!S[w] && D[w] < min) //某点temp未加入s集，且为当前最短路径
			{
				temp = w;
				min = D[w];
			}
		S[temp] = true;
		//更新从源点出发至其余点的最短路径 通过temp
		for (int w = 0; w < n; w++)
			if (!S[w] && D[temp] + G.Edge[temp][w] < D[w])
			{
				D[w] = D[temp] + G.Edge[temp][w];
				Pr[w] = temp;
			}
	}
}
//最短路径 - Bellman_Ford算法  参数：图G、源点v 作用：计算不含负圈图的最短路径 返回是否有圈
bool Bellman_Ford(Graph G, int v)
{
	//初始化
	int n = G.vexnum;//n为图的顶点个数
	for (int i = 0; i < n; i++)
	{
		D[i] = G.Edge[v][i];
		if (D[i] < INF)Pr[i] = v; //v与i连接，v为前驱
		else Pr[i] = -1;
	}
	D[v] = 0;
	//初始化结束，开始双重循环
	for (int i = 2; i<G.vexnum - 1; i++)
		for (int j = 0; j<G.vexnum; j++) //j为源点
			for (int k = 0; k<G.vexnum; k++) //k为终点
				if (D[k] > D[j] + G.Edge[j][k])
				{
					D[k] = D[j] + G.Edge[j][k];
					Pr[k] = j;
				}
	//判断是否含有负圈
	bool flag = true;
	for (int j = 0; j<G.vexnum - 1; j++) //j为源点
		for (int k = 0; k<G.vexnum - 1; k++) //k为终点
			if (D[k] > D[j] + G.Edge[j][k])
			{
				flag = false;
				break;
			}
	return flag;
}
//最短路径 - Floyd_Wallshall算法  参数：图G 作用：计算不含负圈图的最短路径 返回是否有圈
bool Floyd_Wallshall(Graph G)


## 写在最后

**在结束之际，我想重申的是，学习并非如攀登险峻高峰，而是如滴水穿石般的持久累积。尤其当我们步入工作岗位之后，持之以恒的学习变得愈发不易，如同在茫茫大海中独自划舟，稍有松懈便可能被巨浪吞噬。然而，对于我们程序员而言，学习是生存之本，是我们在激烈市场竞争中立于不败之地的关键。一旦停止学习，我们便如同逆水行舟，不进则退，终将被时代的洪流所淘汰。因此，不断汲取新知识，不仅是对自己的提升，更是对自己的一份珍贵投资。让我们不断磨砺自己，与时代共同进步，书写属于我们的辉煌篇章。**


需要完整版PDF学习资源私我





**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**

**需要这份系统化的资料的朋友，可以添加V获取：vip204888 （备注网络安全）**
![img](https://img-blog.csdnimg.cn/img_convert/ff08778a55fe7e0e4d7853284b9d4700.png)

**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**


**在结束之际，我想重申的是，学习并非如攀登险峻高峰，而是如滴水穿石般的持久累积。尤其当我们步入工作岗位之后，持之以恒的学习变得愈发不易，如同在茫茫大海中独自划舟，稍有松懈便可能被巨浪吞噬。然而，对于我们程序员而言，学习是生存之本，是我们在激烈市场竞争中立于不败之地的关键。一旦停止学习，我们便如同逆水行舟，不进则退，终将被时代的洪流所淘汰。因此，不断汲取新知识，不仅是对自己的提升，更是对自己的一份珍贵投资。让我们不断磨砺自己，与时代共同进步，书写属于我们的辉煌篇章。**


需要完整版PDF学习资源私我





**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**

**需要这份系统化的资料的朋友，可以添加V获取：vip204888 （备注网络安全）**
[外链图片转存中...(img-F3D9rroN-1713546183431)]

**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257