图-弗洛伊德（FloydWarshall）算法详解（含全部代码）_弗洛伊德算法代码
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)InsertNode(Graph &G,VexType v
先自我介绍一下，小编浙江大学毕业，去过华为、字节跳动等大厂，目前阿里P7
深知大多数程序员，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
因此收集整理了一份《2024年最新网络安全全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友。
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上网络安全知识点，真正体系化！
由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新
如果你需要这些资料，可以添加V获取：vip204888 （备注网络安全）
正文
}
## 全部代码
/*
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
#include
#include
#include
#include
#include
#include
#include
#include
#include
}
//功能实现函数//
//打印图的顶点表
void PrintVex(Graph G)
{
for (int i = 0; i < G.vexnum; i++)
{
cout << G.Vex[i] << " ";
}
cout << endl;
}
//打印图的弧矩阵
void PrintEdge(Graph G)
{
for (int i = 0; i < G.vexnum; i++)
{
for (int j = 0; j < G.vexnum; j++)
{
if (G.Edge[i][j] == INF)cout << "∞ ";
else cout << G.Edge[i][j] << " ";
}
cout << endl;
}
}
//创建图功能实现函数 参数：图G InsertNode 作用：创建图
void CreateGraph(Graph &G)
{
VexType v, w;
int vn, an;//顶点数，弧数
cout << “请输入顶点数目:” << endl;
cin >> vn;
cout << “请输入弧数目:” << endl;
cin >> an;
cout << “请输入所有顶点名称:” << endl;
for (int i = 0; i<vn; i++)
{
cin >> v;
if (InsertNode(G, v)) continue;//插入点
else {
cout << “输入错误！” << endl; break;
}
}
cout << “请输入所有弧（每行输入起点，终点及权值）:” << endl;
for (int j = 0; j<an; j++)
{
int weight;
cin >> v >> w >> weight;
if (InsertEdge(G, v, w, weight)) continue;//插入弧
else {
cout << “输入错误！” << endl; break;
}
}
cout << “图的顶点及邻接矩阵：” << endl;
PrintVex(G);
PrintEdge(G);
}
//广度遍历功能实现函数 参数：图G 作用：宽度遍历
void BFSTraverse(Graph G)
{
for (int i = 0; i<MaxVerNum; i++)//初始化访问标记数组
{
visited[i] = false;
}
for (int i = 0; i < G.vexnum; i++)//对每个连通分量进行遍历
{
if (!visited[i])BFS(G, i);
}
}
//深度遍历功能实现函数 参数：图G 作用：深度遍历
void DFSTraverse(Graph G)
{
for (int i = 0; i<MaxVerNum; i++)//初始化访问标记数组
{
visited[i] = false;
}
for (int i = 0; i < G.vexnum; i++)//对每个连通分量进行遍历
{
if (!visited[i])
{
DFS(G, i); cout << endl;
}
}
}
//调用最短路径-Dijkstra算法 参数：图G
void Shortest_Dijkstra(Graph &G)
{
char vname;
int v = -1;
cout << “请输入源点名称:” << endl;
cin >> vname;
for (int i = 0; i < G.vexnum; i++)
if (G.Vex[i] == vname)v = i;
if (v == -1)
{
cout << “没有找到输入点！” << endl;
return;
}
Dijkstra(G, v);
cout << “目标点” << “\t” << “最短路径值” << “\t” << “最短路径” << endl;
for (int i = 0; i < G.vexnum; i++)
{
if (i != v)
{
cout << " " << G.Vex[i] << “\t” << " " << D[i] << “\t”;
Path(G, i);
cout << G.Vex[i] << endl;
}
}
}
//调用最短路径- - Bellman_Ford算法 参数：图G
void Shortest_Bellman_Ford(Graph &G)
{
char vname;
int v = -1;
cout << “请输入源点名称:” << endl;
cin >> vname;
for (int i = 0; i < G.vexnum; i++)
if (G.Vex[i] == vname)v = i;
if (v == -1)
{
cout << “没有找到输入点！” << endl;
return;
}
if (Bellman_Ford(G, v))
{
cout << “目标点” << “\t” << “最短路径值” << “\t” << “最短路径” << endl;
for (int i = 0; i < G.vexnum; i++)
{
cout << " " << G.Vex[i] << “\t” << " " << D[i] << “\t”;
Path(G, i);
cout << G.Vex[i] << endl;
}
}
else
{
cout << “输入的图中含有负圈，不能使用该算法！” << endl;
}
}
//调用最短路径- - Floyd_Wallshall算法 参数：图G
void Shortest_Floyd_Wallshall(Graph &G)
{
if (Floyd_Wallshall(G))
{
cout << “最短路径值” << “\t” << “最短路径” << endl;
for (int i = 0; i < G.vexnum; i++)
for (int j = 0; j < G.vexnum; j++)
{
cout << " “<<F_D[i][j] << " \t”;
cout << G.Vex[i];
F_Path(G, i,j);
cout << G.Vex[j] << endl;
}
}
else
{
cout << “输入的图中含有负圈，不能使用该算法！” << endl;
}
}
//菜单
void menu()
{
cout << "1.创建图 2.广度遍历*" << endl;
cout << “3.深度遍历 4.迪杰斯特拉****” << endl;
cout << “5.贝尔曼福特 6.弗洛伊德******” << endl;
cout << “7.退出*************************” << endl;
}
//主函数
int main()
{
int choice = 0;
Graph G;
InitGraph(G);
while (1)
{
menu();
printf(“请输入菜单序号：\n”);
scanf(“%d”, &choice);
if (7 == choice) break;
switch (choice)
{
case 1:CreateGraph(G); break;
case 2:BFSTraverse(G); break;
case 3:DFSTraverse(G); break;
case 4:Shortest_Dijkstra(G); break;
case 5:Shortest_Bellman_Ford(G); break;
case 6:Shortest_Floyd_Wallshall(G); break;
default:printf(“输入错误！！！\n”); break;
}
}
return 0;
}
## 实验结果
实验结果截图
## 最短路径算法比较
| | | | |
| --- | --- | --- | --- |
| 算法\比较内容 | 适用条件 | 算法思想 | 时间复杂度 |
| Dijkstra | 无负权的图，单源或多源 | 贪心 | O(v^2)、O(v^3) |
| Bellman-Ford | 可以有负权但无负圈的图 | 动态规划 | O(v^3)、O(ve) |
| Floyd-Warshall | 无负权的图，多源 | 动态规划 | O(v^3) |
## 写在最后
**在结束之际，我想重申的是，学习并非如攀登险峻高峰，而是如滴水穿石般的持久累积。尤其当我们步入工作岗位之后，持之以恒的学习变得愈发不易，如同在茫茫大海中独自划舟，稍有松懈便可能被巨浪吞噬。然而，对于我们程序员而言，学习是生存之本，是我们在激烈市场竞争中立于不败之地的关键。一旦停止学习，我们便如同逆水行舟，不进则退，终将被时代的洪流所淘汰。因此，不断汲取新知识，不仅是对自己的提升，更是对自己的一份珍贵投资。让我们不断磨砺自己，与时代共同进步，书写属于我们的辉煌篇章。**
需要完整版PDF学习资源私我
**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**
**需要这份系统化的资料的朋友，可以添加V获取：vip204888 （备注网络安全）**
**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**
**在结束之际，我想重申的是，学习并非如攀登险峻高峰，而是如滴水穿石般的持久累积。尤其当我们步入工作岗位之后，持之以恒的学习变得愈发不易，如同在茫茫大海中独自划舟，稍有松懈便可能被巨浪吞噬。然而，对于我们程序员而言，学习是生存之本，是我们在激烈市场竞争中立于不败之地的关键。一旦停止学习，我们便如同逆水行舟，不进则退，终将被时代的洪流所淘汰。因此，不断汲取新知识，不仅是对自己的提升，更是对自己的一份珍贵投资。让我们不断磨砺自己，与时代共同进步，书写属于我们的辉煌篇章。**
需要完整版PDF学习资源私我
**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**
**需要这份系统化的资料的朋友，可以添加V获取：vip204888 （备注网络安全）**
[外链图片转存中...(img-xsxVeu0W-1713546208454)]
**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
3
0- 0
已为社区贡献5条内容
所有评论(0)