Floyd算法求图最短路径问题（基于邻接矩阵）

什么是图的最短路径？

就是给出两个带权图中的顶点，求出这个两个顶点之间权值或者说代价最小的路径。

算法思想

在图的最短路径问题上，相比于dijkstra算法求解单源最短路径，Floyd算法可以很好解决各个顶点之间的最短路径问题。个人总结：Floyd算法核心就是一种利用动态规划，求解问题，核心就是关于中转点的引入是否会引起最短路径变化展开思考

在之前，我们考虑最短路径问题时候，一般是从当前点出发，查看当前点的最短路径顶点，但是这个最短路径是对于相邻点，对于不相邻的点，最短路径会发生变化，变化的产生就是“中转点”的引入，在中转点的帮助下，两点的最短路径就会变化，这也是算法设计的初衷，就是探讨中转点引入带来的变化。

下面是实现算法的核心代码

void Floyd(MGraph &g) {
	//初始化一个path矩阵
	MGraph path = PreparePathGraph(g.vertex_number);

	//遍历每一条边，开始比较在引入中转点之后的权值大小
	for (int i = 0; i < g.vertex_number; i++)
	{
		for (int j = 0; j < g.vertex_number; j++)
		{
				for (int k = 0; k < g.vertex_number; k++)
				{
					if (g.edge[i][j] > g.edge[i][k] + g.edge[k][j]) {
						g.edge[i][j] = g.edge[i][k] + g.edge[k][j];
						path.edge[i][j] = k;//保存顶点信息
						
					}
				}
		}
	}
}

具体的说明：path矩阵是用于保存路径信息的矩阵，所存储的单元信息为-1，表示没有中转点信息，为其他值，即中转点的索引？或者是各种能代表中转点的信息。

g.edge[i][j] > g.edge[i][k] + g.edge[k][j]

当当前边的代价大于加入第k个顶点作为中转点的代价和，说明引入第k个顶点作为第i个顶点到底k个顶点之间的中转点时，代价更小，这个时候就修改图g的边的信息，并修改path矩阵对应单元的信息，存入k顶点的信息。

结果演示

 原始矩阵，例V0->V1有有向边，代价为6

Floyd算法告诉我们，解决一个问题时候，要先分析问题，问题的变量改变因子，找到因子成分，从点入手改变面

附

所使用的邻接矩阵数据结构

//顶点的数据结构
typedef struct {
	int data;//int数据
	char ch;//字符数据
	int info;//顶点的权值
	bool empty;//顶点是否存在
}item;

//定义邻接矩阵
typedef struct{
	item vertexs[VERTEXS_MAXSIZE];
	int edge[VERTEXS_MAXSIZE][VERTEXS_MAXSIZE];
	int vertex_number,arc_number;//顶点vertex和边arc的个数
}MGraph;

//初始化邻接矩阵
void InitAdjGraph(MGraph& g) {
	//将图的顶点数和边数初始化为0
	g.vertex_number = 0;
	g.arc_number = 0;
}

准备的path矩阵函数

//准备一个path邻接矩阵，记录每个顶点之间最短路径的中转点信息
MGraph PreparePathGraph(int vertex_number) {
	//新建一个path矩阵
	MGraph path;
	InitAdjGraph(path);
	path.vertex_number = vertex_number;//让path数组的顶点个数和源矩阵的顶点同步
	for (int i = 0; i < vertex_number; i++)
	{
		//在顶点集里面添加顶点
		path.vertexs[i].data = i;//数字为i
		for (int j = 0; j < vertex_number; j++)
		{
			path.edge[i][j] = -1;//-1表示没有中转点
		}
	}
	return path;
}