弗洛伊德算法用于计算图中任意两点间的最短路径（简化的版本）
发布时间
阅读量：
阅读量
弗洛伊德算法思想：
用于存储任意两点之间的最短路径信息，在弗洛伊德算法开始执行时，在邻接矩阵的基础上初始化一个距离矩阵D，在此过程中通过弗洛伊德算法逐步计算每对顶点之间可能存在的最短路径长度。随后系统会依次循环遍历所有顶点作为中间节点k，在此过程中对每对顶点(i,j)进行判断：若从i出发经k到j的距离小于直接从i到j的直线距离，则更新对应位置即为该较短距离值。
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f
int D[100][100],N,M,G[100][100]; //D为任意两点最短路径矩阵 G为邻接矩阵
void flyod()
{
int i,j,k;
for(k=1;k<=N;k++) //枚举中转点
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{ if(D[i][k]+D[k][j]<D[i][j]) //当任意两点经过中转点比两点间直接距离短时，松弛这两点最短路的值
D[i][j]=D[i][k]+D[k][j];
}
for(i=1;i<=N;i++) //全部评论 (0)
还没有任何评论哟~