Floyd 算法：动态规划中的最短路径问题

一、简介

Floyd 算法是一种用于求解图中所有顶点对之间最短路径的动态规划算法。它是由 Robert W. Floyd 在 1965 年提出的，因此得名 Floyd-Warshall 算法。该算法的核心思想是使用动态规划来避免重复计算已经计算过的子问题的解。

二、原理

假设有 n 个顶点的图 G(用邻接矩阵表示),我们需要求解所有顶点对之间的最短路径。设 f[i][j] 表示从顶点 i 到顶点 j 的最短路径长度。我们的目标是求解 f[i][j],其中 i < j 且 i, j∈V(G)。

Floyd 算法的基本思想是：对于任意两个顶点 i 和 j,如果通过顶点 k 可以使 i 到 j 的路径长度更短，那么更新

这里的 k 是中间顶点，可以是任何与 i 和 j 相邻的顶点。

Floyd 算法的时间复杂度为 O(n^3),空间复杂度为 O(n^2)。为了降低时间复杂度，可以使用压缩矩阵来存储邻接矩阵。

三、C++ 代码实现

#include<bits/stdc++.h> // 引入常用的C++库
#define reg register // 定义宏，将变量声明为寄存器类型
using namespace std; // 使用标准命名空间

// 读取输入的整数
inline int read(){
	int x=0,f=1;
	char ch=getchar(); // 获取输入的第一个字符
	while(ch<'0'||ch>'9'){ // 如果字符不是数字
		if(ch=='-') f=-1; // 如果是负号，设置标志位为负数
		ch=getchar(); // 继续获取下一个字符
	}
	while(ch>='0'&&ch<='9'){ // 如果字符是数字
		x=(x<<1)+(x<<3)+(ch^48); // 将字符转换为整数并累加到结果中
		ch=getchar(); // 继续获取下一个字符
	}
	return x*f; // 返回结果，如果有负号则返回负数
}

// 输出整数，如果是负数则在前面加上负号
void write(int x){
	if(x<0){
		putchar('-');
		x=-x; // 将负数转换为正数
	}
	if(x>9) write(x/10); // 如果数字大于9,递归调用write函数处理十位数
	putchar(x%10+'0'); // 将个位数输出
	return ;
}

const int MAXN=102,MAXM=4502; // 定义常量，表示矩阵的最大行数和列数
int n,m,d[MAXN][MAXN]; // 定义二维数组d,用于存储最小生成树的权重

int main(){
	n=read(),m=read(); // 读取输入的两个整数n和m
	memset(d,0x3f,sizeof(d)); // 将二维数组d的所有元素初始化为无穷大
	for(reg int i=1;i<=n;i++) d[i][i]=0; // 将对角线上的元素设置为0,因为从一个点到自身的距离为0
	for(reg int i=1;i<=m;i++){ // 对于每条边(u, v, w)
		int u=read(),v=read(),w=read(); // 读取边的起点、终点和权重
		d[u][v]=min(d[u][v],w); // 更新d[u][v]为当前边的权重和d[u][v]中的较小值
		d[v][u]=min(d[v][u],w); // 更新d[v][u]为当前边的权重和d[v][u]中的较小值
	}
	for(reg int k=1;k<=n;k++){ // 对于每个顶点k,计算其所有邻居节点之间的最小生成树的权重之和
		for(reg int i=1;i<=n;i++){
			for(reg int j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]); // 更新d[i][j]为当前边的权重和d[i][j]中的较小值加上从顶点k到其他节点的最小生成树的权重之和
			}
		}
	}
	for(reg int i=1;i<=n;i++){ // 对于每个顶点i,输出其到其他所有顶点的最短路径的权重之和
		for(reg int j=1;j<=n;j++){
			printf("%d ",d[i][j]); // 按照题目要求的格式输出权重之和
		}
		printf("\n"); // 每行输出完毕后换行
	}
	return 0; // 程序正常结束
}