算法作业2.1----- Floyd算法求解各个顶点的最短距离

程序员文章站 2024-03-16 14:09:34

...

1. 问题

用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵），按实验报告模板编写算法。
算法作业2.1----- Floyd算法求解各个顶点的最短距离

2. 解析

Floyd算法：
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法

核心思路为：

路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

状态转移方程
其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。

问题解决思路：
由Floyd算法可得：

一、如果某个节点位于从起点到终点的最短距离路径上：则起点到终点的最短距离路径就等于起点到该节点的距离加上该节点到终点的距离。

二、如果某个节点不在从起点到终点的最短距离路径上：则起点到终点的最短距离路径就小于起点到该节点的距离加上该节点到终点的距离。

举个例子：再上图中节点1到节点3的距离有3条：分别为:V1——>V3，V1——>V2——>V3,V1——>V4——>V3。在三条边中V1——>V2——>V3的距离最短，所以节点2在最短路径上，节点4不再短路径上，所以节点1到节点2加上节点2到节点3的距离等于节点1到3的最短距离，而节点1到节点4加上节点4到节点3 的距离大于节点1到3的最短路径。

矩阵的最初距离矩阵为：（INF为最大）
算法作业2.1----- Floyd算法求解各个顶点的最短距离

3. 设计

int D[max][max]={/*输入最初的距离矩阵*/};  //表示图中各个节点之间的路径，如D[i][j]，就为Vi——>Vj权值为D[i][j]
int S[max][max];  //表示图中节点的后继矩阵,如S[i][j]，则Vi——>Vj的最短路径的存在V S[i][j].
for(i到V){ //对S进行初始化
	count=0;
	for(j到V){
		if（i!=j）{
			S[i][j]=count;
		}
		else{
			S[i][j]=-1;
		}
		++count;
	}
}
for(k到V) //V表示节点的数量
	for(i到V)
		for(j到V)
			if(D[i][k]+D[k][j]<D[i][j]){
				D[i][j]=D[i][k]+D[k][j];
				S[i][j]=S[i][k];
			}
for(i到V){ 
	for(j到V)
		//输出距离矩阵。
}