博客

给定带权有向图 G=（V, E）,  对任意顶点vi,vj 属于V,(i!=j) 求顶点vi到顶点vj的最短路径

解决办法: 弗洛伊德提出的求各个顶点之间的最短路径算法—–Floyd算法

基本思想


:(利用循环，依次把0，1，2，……n顶点添加到路径上看路径权值矩阵是否发生变化)

路径矩阵表示的是任意两个顶点之间的权值

1.用图中的权值去初始化A[][]数组，  将path[][]全部初始化为-1；

首先对于n个顶点的图G，求任意一对顶点 Vi –> Vj之间的最短路径，可以分为下面几个阶段。

# 初始：不允许在其他顶点中转，最短路径是？？                                                                        (最短路径就是图中权值组成的n*n的矩阵,  n代表顶点个数)

#0: 若允许V0中转， 最短路径是?

#1：若允许V0，V1中转，最短路径是?           ………..

#n-1： 若允许V0， V1，V2，……..V(n-1)中转，最短路径是

例如, 图结构为:

初始化A[][]数组 和 path[][] 数组.

首先需要一个A[]矩阵和path[]矩阵;

有n个顶点，所以需要循环n趟。
for(int k=0; k<n; k++){     //有n个顶点，用来表示将n个顶点一次加入
	for(int i=0; i<n; i++){         
		for(int j=0; j<n; j++){          //这两层循环用来看A[][]数组和path[]数组
			 //如果加入k顶点后，i到k到j的权值 小于 i到j的权值，则需要更新A[][]数组和path[][]数组
            if(A[i][j]>A[i][k]+A[k][j]){  
				A[i][j]=A[i][k] + A[k][j];
				path[i][j]=k; 
			}	
		}
	}
}