C语言-数据结构 弗洛伊德算法(Floyd)邻接矩阵存储

        弗洛伊德算法相比迪杰斯特拉相似的地方都是遍历邻接矩阵不断调整最短路径的信息，并且两种算法面对多源最短路径的时间复杂度都是O(n^3)，Floyd采用的是动态规划而Dijkstra是采用贪心的思想。在Floyd中我们将创建两个数组进行辅助，一个path二维数组用于存储路径信息，一个table二维数组用于记录更新各结点间的最短路径长度，table的初始化就是简单的把邻接矩阵的信息复制过来，整个算法都是在这个table表中不断更新，代码中第一层for循环是控制中转结点，另外两行就是遍历整个table二位数组，table[v][k]表示辅助列，table[k][w]表示辅助行，辅助行与辅助列由中转结点控制在整个table表的主对角线上运动，table[v][w]当前扫描的邻接结点信息，如果当前邻接结点的权值大于对应的（辅助行+辅助列的权值和），那么说明找到更短的路径需要进行更新权值，当前邻接结点信息改为（辅助行+辅助列的权值和），同时更新路径信息为中转结点（即前驱顶点），代码中path[v][k]存储了对应的中转结点信息，利用它更新当前邻接结点的前驱结点（对应的中转结点）信息，当循环结束整个图各顶点到达其他所有顶点的最短距离就计算完成了，最后我们打印table矩阵的上三角部分因为两个结点的表示可以用一个方向就行，例如A->F打印了就可以表示F->A，并不需求遍历完全部table矩阵信息，同时打印路径信息的第二个for循环有个+1操作是为了避免打印AA、BB这种自己到自己的路径，也就是不打印主对角线，path路径信息的存储也同样用到并查集的部分思想在上一篇博文提过，在代码中通过不断循环path路径能够找到它的前驱结点一步步把所有路径结点信息找到，相比迪杰斯特拉倒着找结点信息，这里我们可以之间通过path二维数组顺序查找到路径信息，也是非常巧妙的！

 我们将创建下面的无向权值图：

84ef03cba4ba478383b338ae5884012a.png

  邻接矩阵的绘制还是手动赋值上三角，并通过矩阵对称性生成整个邻接矩阵，其中最小生成树中需要用到权值，对应原本有边的地方之前我是用1表示，现在改成边对应的权值，之前的0表示没有边，现在改成99表示为无穷，其实应该换成更大的值以确保树的边权值都小于这个最大值，但为了方便对齐显示看邻接矩阵，就使用了比本图中各边长较大的99来表示最大值。

9eefaa5c866742cbb239f5f9de2aff7d.png

Floyd算法代码：

//存储所有顶点的路径信息
typedef int Patharc[MAXVEX][MAXVEX];
//最短路径表copy邻接矩阵，不断扫描更新各顶点相互间的最短距离
typedef int ShortestPathTable[MAXVEX][MAXVEX];
// Floyd算法实现
void Floyd(MGraph G, Patharc path, ShortestPathTable table) {
	int v, w, k;
	// 初始化表和路径矩阵
	for (v = 0; v < G.numNodes; v++) {
		for (w = 0; w < G.numNodes; w++) {
			table[v][w] = G.arc[v][w];  // 初始化最短路径表
			if (G.arc[v][w] < INFINITY) {
				path[v][w] = w;  // 有直接边时，路径是目标顶点
			}
			else {
				path[v][w] = -1; // 如果没有边，则设为 -1
			}
		}
	}

	// Floyd算法的核心计算
	for (k = 0; k < G.numNodes; k++) {  // 遍历每个顶点作为中间顶点
		for (v = 0; v < G.numNodes; v++) {  // 遍历起点
			for (w = 0; w < G.numNodes; w++) {  // 遍历终点
				// 如果通过顶点 k 的路径更短，则更新路径和最短路径表
				if (table[v][w] > table[v][k] + table[k][w]) {
					table[v][w] = table[v][k] + table[k][w];
					path[v][w] = path[v][k];
				}
			}
		}
	}

	// 打印各顶点间的最短路径
	printf("各顶点间最短路径如下：\n");
	for (v = 0; v < G.numNodes; v++) {
		for (w = v + 1; w < G.numNodes; w++) {  // 遍历每对顶点
			//Array数组存储顶点ABCDEFGH
			printf("%c-%c weight:%d\n", Array[v], Array[w], table[v][w]);
			k = path[v][w];  // 从起点到终点的路径
			printf("path:%d", v);
			while (k != w) {  // 路径输出
				printf("->%d", k);
				k = path[k][w];
			}
			printf("->%d\n", w);
		}
		printf("\n");
	}
}

完整代码（包括邻接矩阵的创建、Floyd算法）

#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"

// 禁用特定的警告
#pragma warning(disable:4996)

// 定义一些常量和数据类型
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 8 /* 最大顶点数，用户定义 */
#define MAXEDGE 10 /* 最大边数，用户定义 */
#define GRAPH_INFINITY 99 /* 用0表示∞，表示不存在边 */

/* 定义状态、顶点和边的类型 */
typedef int Status;  /* Status是函数的返回类型，如OK表示成功 */
typedef char VertexType; /* 顶点的类型，用字符表示 */
typedef int EdgeType; /* 边上的权值类型，用整数表示 */
typedef int Boolean; /* 布尔类型 */
// 定义顶点标签
char Array[] = "ABCDEFGHI";

/* 图的邻接矩阵结构体 */
typedef struct
{
	VertexType vexs[MAXVEX]; /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，表示边的权值 */
	int numNodes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;

//存储所有顶点的路径信息
typedef int Patharc[MAXVEX][MAXVEX];
//最短路径表copy邻接矩阵，不断扫描更新各顶点相互间的最短距离
typedef int ShortestPathTable[MAXVEX][MAXVEX];

/* 创建一个无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{
	int i, j, k, w;
	// 初始化图的顶点数和边数
	G->numNodes = 8;
	G->numEdges = 10;
	// 初始化邻接矩阵和顶点表
	for (i = 0; i < G->numNodes; i++) {
		for (j = 0; j < G->numNodes; j++) {
			G->arc[i][j] = GRAPH_INFINITY; /* 初始化邻接矩阵为∞ */
		}
		G->vexs[i] = Array[i]; /* 初始化顶点表 */
	}
	G->arc[0][0] = GRAPH_INFINITY;
	G->arc[0][1] = 10;
	G->arc[0][2] = GRAPH_INFINITY;
	G->arc[0][3] = GRAPH_INFINITY;
	G->arc[0][4] = GRAPH_INFINITY;
	G->arc[0][5] = 11;
	G->arc[0][6] = GRAPH_INFINITY;
	G->arc[0][7] = GRAPH_INFINITY;

	G->arc[1][0] = GRAPH_INFINITY;
	G->arc[1][1] = GRAPH_INFINITY;
	G->arc[1][2] = 23;
	G->arc[1][3] = GRAPH_INFINITY;
	G->arc[1][4] = GRAPH_INFINITY;
	G->arc[1][5] = GRAPH_INFINITY;
	G->arc[1][6] = 12;
	G->arc[1][7] = GRAPH_INFINITY;

	G->arc[2][0] = GRAPH_INFINITY;
	G->arc[2][1] = GRAPH_INFINITY;
	G->arc[2][2] = GRAPH_INFINITY;
	G->arc[2][3] = 21;
	G->arc[2][4] = GRAPH_INFINITY;
	G->arc[2][5] = GRAPH_INFINITY;
	G->arc[2][6] = GRAPH_INFINITY;
	G->arc[2][7] = GRAPH_INFINITY;

	G->arc[3][0] = GRAPH_INFINITY;
	G->arc[3][1] = GRAPH_INFINITY;
	G->arc[3][2] = GRAPH_INFINITY;
	G->arc[3][3] = GRAPH_INFINITY;
	G->arc[3][4] = GRAPH_INFINITY;
	G->arc[3][5] = GRAPH_INFINITY;
	G->arc[3][6] = GRAPH_INFINITY;
	G->arc[3][7] = 11;

	G->arc[4][0] = GRAPH_INFINITY;
	G->arc[4][1] = GRAPH_INFINITY;
	G->arc[4][2] = GRAPH_INFINITY;
	G->arc[4][3] = GRAPH_INFINITY;
	G->arc[4][4] = GRAPH_INFINITY;
	G->arc[4][5] = 47;
	G->arc[4][6] = GRAPH_INFINITY;
	G->arc[4][7] = 80;

	G->arc[5][0] = GRAPH_INFINITY;
	G->arc[5][1] = GRAPH_INFINITY;
	G->arc[5][2] = GRAPH_INFINITY;
	G->arc[5][3] = GRAPH_INFINITY;
	G->arc[5][4] = GRAPH_INFINITY;
	G->arc[5][5] = GRAPH_INFINITY;
	G->arc[5][6] = 6;
	G->arc[5][7] = GRAPH_INFINITY;

	G->arc[6][0] = GRAPH_INFINITY;
	G->arc[6][1] = GRAPH_INFINITY;
	G->arc[6][2] = GRAPH_INFINITY;
	G->arc[6][3] = GRAPH_INFINITY;
	G->arc[6][4] = GRAPH_INFINITY;
	G->arc[6][5] = GRAPH_INFINITY;
	G->arc[6][6] = GRAPH_INFINITY;
	G->arc[6][7] = 8;

	G->arc[7][0] = GRAPH_INFINITY;
	G->arc[7][1] = GRAPH_INFINITY;
	G->arc[7][2] = GRAPH_INFINITY;
	G->arc[7][3] = GRAPH_INFINITY;
	G->arc[7][4] = GRAPH_INFINITY;
	G->arc[7][5] = GRAPH_INFINITY;
	G->arc[7][6] = GRAPH_INFINITY;
	G->arc[7][7] = GRAPH_INFINITY;

	// 由于是无向图，邻接矩阵是对称的，需要将其对称
	for (int i = 0; i < G->numNodes; i++) {
		for (int j = 0; j < G->numNodes; j++) {
			G->arc[j][i] = G->arc[i][j];
		}
	}
	// 打印邻接矩阵
	printf("邻接矩阵为：\n");
	printf("     ");
	for (int i = 0; i < G->numNodes; i++) {
		printf("%2d ", i); /* 打印列索引 */
	}
	printf("\n     ");
	for (int i = 0; i < G->numNodes; i++) {
		printf("%2c ", G->vexs[i]); /* 打印顶点标签 */
	}
	printf("\n");
	for (int i = 0; i < G->numNodes; i++) {
		printf("%2d", i); /* 打印行索引 */
		printf("%2c ", G->vexs[i]); /* 打印顶点标签 */
		for (int j = 0; j < G->numNodes; j++) {
			if (G->arc[i][j] != 99) {
				printf("\033[31m%02d \033[0m", G->arc[i][j]); /* 打印邻接矩阵中的权值 */
			}
			else {
				printf("%02d ", G->arc[i][j]); /* 打印邻接矩阵中的权值 */
			}
		}
		printf("\n");
	}
}

// Floyd算法实现
void Floyd(MGraph G, Patharc path, ShortestPathTable table) {
	int v, w, k;
	// 初始化表和路径矩阵
	for (v = 0; v < G.numNodes; v++) {
		for (w = 0; w < G.numNodes; w++) {
			table[v][w] = G.arc[v][w];  // 初始化最短路径表
			if (G.arc[v][w] < INFINITY) {
				path[v][w] = w;  // 有直接边时，路径是目标顶点
			}
			else {
				path[v][w] = -1; // 如果没有边，则设为 -1
			}
		}
	}

	// Floyd算法的核心计算
	for (k = 0; k < G.numNodes; k++) {  // 遍历每个顶点作为中间顶点
		for (v = 0; v < G.numNodes; v++) {  // 遍历起点
			for (w = 0; w < G.numNodes; w++) {  // 遍历终点
				// 如果通过顶点 k 的路径更短，则更新路径和最短路径表
				if (table[v][w] > table[v][k] + table[k][w]) {
					table[v][w] = table[v][k] + table[k][w];
					path[v][w] = path[v][k];
				}
			}
		}
	}

	// 打印各顶点间的最短路径
	printf("\n各顶点间最短路径如下：\n");
	for (v = 0; v < G.numNodes; v++) {
		for (w = v + 1; w < G.numNodes; w++) {  // 遍历每对顶点
			//Array数组存储顶点ABCDEFGH
			printf("%c-%c weight:%d\n", Array[v], Array[w], table[v][w]);
			k = path[v][w];  // 从起点到终点的路径
			printf("path:%d", v);
			while (k != w) {  // 路径输出
				printf("->%d", k);
				k = path[k][w];
			}
			printf("->%d\n", w);
		}
		printf("\n");
	}
}

// 主函数
int main(void) {
	MGraph G;
	/* 创建图 */
	CreateMGraph(&G);  // 创建并初始化图 G
	Patharc path;
	ShortestPathTable table;
	Floyd(G, path, table);  // 计算最短路径
	return 0;
}

 无向权值图：

84ef03cba4ba478383b338ae5884012a.png

运行结果：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/878781.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

sqlgun靶场训练

sqlgun靶场训练

1.看到php&#xff1f;id &#xff0c;然后刚好有个框&#xff0c;直接测试sql注入 2.发现输入1 union select 1,2,3#的时候在2处有回显 3.查看表名 -1 union select 1,group_concat(table_name),3 from information_schema.tables where table_schemadatabase()# 4.查看列名…
阅读更多...
磁盘写入缓存区太大，如何清理C盘缓存

磁盘写入缓存区太大，如何清理C盘缓存

针对“磁盘写入缓存区太大&#xff0c;如何清理C盘缓存”的问题&#xff0c;我们可以从多个角度进行专业解答。首先&#xff0c;需要明确的是&#xff0c;“磁盘写入缓存区太大”这一表述可能涉及硬盘缓存的设置或系统缓存管理&#xff0c;但通常用户面对的问题更多是关于C盘空…
阅读更多...
极速上云2.0范式：一键智连阿里云

极速上云2.0范式：一键智连阿里云

在传统上云的现状与挑战&#xff1a; 专线上云太重&#xff0c;VPN上云不稳&#xff0c;云上VPC&#xff0c;云下物理网络&#xff0c;多段最后一公里...... 层层对接&#xff0c;跳跳延迟&#xff0c;好生复杂! 当你试图理解SD-WAN供应商和阿里云的文档&#xff0c;以协调路由…
阅读更多...
【23-24年】年度总结与迎新引荐

【23-24年】年度总结与迎新引荐

文章目录 相关连接前言1 忙碌的备研与本科毕设2 暑期阿里之旅3 团队荣誉与迎新引荐4 项目合作意向 相关连接 个人博客&#xff1a;issey的博客 - 愿无岁月可回首 前言 自从2023年4月更新了两篇关于NLP的文章后&#xff0c;我便消失了一年半的时间。如今&#xff0c;随着学业…
阅读更多...
[000-01-008].第05节：OpenFeign特性-重试机制

[000-01-008].第05节：OpenFeign特性-重试机制

我的后端学习大纲 SpringCloud学习大纲 1.1.重试机制的默认值&#xff1a; 1.重试机制默认是关闭的&#xff0c;给了默认值 1.2.测试重试机制的默认值&#xff1a; 1.3.开启Retryer功能&#xff1a; 1.修改配置文件YML的配置&#xff1a; 2.新增配置类&#xff1a; packa…
阅读更多...
STM32启用FPU浮点运算

STM32启用FPU浮点运算

这篇文章产生背景&#xff1a;其他人的文章太杂了&#xff0c;对我这种菜鸡无法接受&#xff1b; 参考文章&#xff1a; stm32h743单片机嵌入式学习笔记7-FPU_stmh743vit4-CSDN博客 stm32F407 打开 FPU(浮点运算处理器)_stm32f407开启fpu-CSDN博客 STM32F4CubeMXHal库下使能…
阅读更多...
视频格式转为mp4（使用ffmpeg）

视频格式转为mp4（使用ffmpeg）

1、首先安装ffmpeg&#xff0c;下载链接如下 https://www.gyan.dev/ffmpeg/builds/packages/ffmpeg-6.1.1-full_build.7z 安装后确保ffmpeg程序加到PATH路径里&#xff0c;cmd执行ffmpeg -version出现下图内容表示安装成功。 2、粘贴下面的脚本到文本文件中&#xff0c;文件后缀…
阅读更多...
CVTE-嵌入式面经一面面经准备（已通过）

CVTE-嵌入式面经一面面经准备（已通过）

目录&#xff1a; 目录&#xff1a; 一、9.9面经 1.1 什么是嵌入式&#xff1f; 1. 特点&#xff1a; 2. 应用领域&#xff1a; 3. 示例&#xff1a; 1.2 嵌入式设备开发与电脑上软件开发的区别 1. 硬件资源限制&#xff1a; 2. 操作系统&#xff1a; 3. 开发工具&#xff1a; …
阅读更多...
K1计划100%收购 MariaDB； TDSQL成为腾讯云核心战略产品； Oracle@AWS/Google/Azure发布

K1计划100%收购 MariaDB； TDSQL成为腾讯云核心战略产品； Oracle@AWS/Google/Azure发布

重要更新 1. 腾讯全球数字生态大会与9月5日-6日举行&#xff0c;发布“5T”战略&#xff0c;包括TDSQL、TencentOS、TCE&#xff08;专有云 &#xff09;、TBDS&#xff08;大数据&#xff09;、TI &#xff08;人工智能开发平台&#xff09;等 ( [2] ) ; 并正式向原子开源基金…
阅读更多...
学习笔记（一）

学习笔记（一）

前言 一、对象 1、由类建模而成&#xff0c;是消息、数据和行为的组合 2、可以接收和发送消息&#xff0c;并利用消息进行彼此的交互。消息要包含传送给对象接收的信息 3、类的实例化&#xff1a;把类转换为对象的过程叫类的实例化。 4、对象的特性 (1) 对象有状态&#…
阅读更多...
深度揭秘：日志打印的艺术与实战技巧，让你的代码会说话！

深度揭秘：日志打印的艺术与实战技巧，让你的代码会说话！

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;Linux从入门到进阶 欢迎大家点赞收藏评论&#x1f60a; 目录 &#x1f341;日志&#x1f342;日志分模块实现讲解&#x1f343;日志等级的实现&#x1f965;日志时间*时间的获取* &#x1f308;文…
阅读更多...
[数据集][目标检测]汽车头部尾部检测数据集VOC+YOLO格式5319张3类别

[数据集][目标检测]汽车头部尾部检测数据集VOC+YOLO格式5319张3类别

数据集制作单位&#xff1a;未来自主研究中心(FIRC) 版权单位&#xff1a;未来自主研究中心(FIRC) 版权声明&#xff1a;数据集仅仅供个人使用&#xff0c;不得在未授权情况下挂淘宝、咸鱼等交易网站公开售卖,由此引发的法律责任需自行承担 数据集格式&#xff1a;Pascal VOC格…
阅读更多...
[数据集][目标检测]烟叶病害检测数据集VOC+YOLO格式612张3类别

[数据集][目标检测]烟叶病害检测数据集VOC+YOLO格式612张3类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;612 标注数量(xml文件个数)&#xff1a;612 标注数量(txt文件个数)&#xff1a;612 标注类别…
阅读更多...
如何在 Vue 3 + Element Plus 项目中实现动态设置主题色以及深色模式切换

如何在 Vue 3 + Element Plus 项目中实现动态设置主题色以及深色模式切换

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 一、引言二、项目依赖和环境配置1. VueUse2. use-element-plus-theme3. 安装依赖 三、实现深色模式切换1. 设置深色模式状态2. 模板中的深色模式切换按钮3. 深色模式的效果展示 四、动态切换主题色五、总结 一、引言 在现代…
阅读更多...
C# 比较对象新思路，利用反射技术打造更灵活的比较工具

C# 比较对象新思路，利用反射技术打造更灵活的比较工具

前言 嘿&#xff0c;大家好&#xff01;如果你之前看过我分享的文章《C# 7个方法比较两个对象是否相等》&#xff0c;你可能会意识到对象比较在实际业务中经常出现的场景。今天&#xff0c;我想继续与大家分享一个在实际项目中遇到的问题。 有一次&#xff0c;我接手了一个别…
阅读更多...
Qt多元素控件——QTreeWidget

Qt多元素控件——QTreeWidget

文章目录 QTreeWidgetQTreeWidget核心方法及信号QTreeWidgetItem核心属性及方法 QTreeWidget使用示例 QTreeWidget QTreeWidget表示树形控件&#xff0c;里面每个元素都是一个QTreeWidgetItem&#xff0c;每个QTreeWidgetItem可以包含多个文本和图标&#xff0c;每个文本/图标…
阅读更多...
SEGGERS实时系统embOS推出Linux端模拟器

SEGGERS实时系统embOS推出Linux端模拟器

SEGGER 发布了两个新的 embOS 仿真模拟器&#xff1a;embOS Sim Linux 和 embOS-MPU Sim Linux。 通过模拟 Linux 主机系统上的硬件&#xff0c;取代物理硬件&#xff0c;为开发人员提供了一种无缝的方式来构建原型和测试应用程序。 embOS Sim Linux 端口支持 32 位和 64 位系…
阅读更多...
第313题｜解积分不等式题目的5种方法常用方法｜武忠祥老师每日一题

第313题｜解积分不等式题目的5种方法常用方法｜武忠祥老师每日一题

解题思路&#xff1a;把多阶次积分和函数值联系起来&#xff0c;应该想到泰勒公式。 本题应该使用带有拉格朗日余项的泰勒公式&#xff1a; 方法一&#xff1a; 等式左右两边进行积分&#xff0c;右边第一项常数项不变&#xff0c;第二项&#xff08;x-1/2&#xff09;积完之…
阅读更多...
371. 两整数之和

371. 两整数之和

目录 一&#xff1a;题目&#xff1a; 二&#xff1a;代码&#xff1a; 三&#xff1a;结果&#xff1a; 一&#xff1a;题目&#xff1a; 给你两个整数 a 和 b &#xff0c;不使用 运算符 和 - &#xff0c;计算并返回两整数之和。 示例 1&#xff1a; 输入&#xff1a;…
阅读更多...
★ C++进阶篇 ★ 多态

★ C++进阶篇 ★ 多态

Ciallo&#xff5e;(∠・ω< )⌒☆ ~ 今天&#xff0c;我将继续和大家一起学习C进阶篇第一章----多态 ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页&#xff1a;椎名澄嵐-CSDN博客 C基础篇专栏&#xff1a;★ C基础篇 ★_椎名澄嵐的博客-CSDN博客 …
阅读更多...
最新文章

Copyright @ 2022~2023