本文共 789 字，大约阅读时间需要 2 分钟。

这个算法其实是在基于动态规划算法之上（类似于01背包）进行设想的

设Di,j,k为从i到j的只以(1…k)集合中结点为中间结点的最短路径的长度，那么按照01背包的思维就是1.从顶点I到顶点J是不经过K的，那么就是Dijk-1,2.如果确实经过k的话，就把两个顶点拆分成两个部分Dikk-1+Djkk-1

然后使用三次循环，来求对应的值。

最后可以将三维的数组变成二维的数组

三维数组形式：

void floyd(){
   	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			dis[i][j][0]=map[i][j];	for(int k=1;k<=n;k++)		for(int i=1;i<=n;i++)			for(int j=1;j<=n;j++)			{
   				dis[i][j][k]=dis[i][j][k-1];				if(dis[i][j][k]>dis[i][k][k-1]+dis[k][j][k-1])					dis[i][j][k]=dis[i][k][k-1]+dis[k][j][k-1];			}}

二维数组形式：

for(int k =1 ;  k <= n ; k ++ ){
         for(int i =1 ; i<= n ; i++){
             for(int j =1 ;j<=n;j++){
                    dist[ i ][ j ]= min( dist[ i ][ j ],dist[ i ][ k ]+dist[ k ][ j ] );                  }       }  }

总结下来，弗洛伊德算法比较适合多个起点和多个终点，而迪杰特斯拉算法更加适合唯一的起点和终点。

转载地址：http://skfen.baihongyu.com/