弗洛伊德算法
弗洛伊德算法的原理是动态规划
设D[i][j][k]为从i到j只以1-k中的结点为中间结点的最短路径长度，则
(1)如果最短距离经过点k，那么D[i][j][k] = D[i][k][k - 1] + D[k][j][k - 1]
(2)如果不经过点k，那么D[i][j][k] = D[i][j][k - 1]
因此，D[i][j][k] = Min(D[i][k][k - 1] + D[k][j][k - 1], D[i][j][k - 1])
显然，把k放在最外层的循环，即可省略第三维
下面代码的结点如图：
#include <iostream>
using namespace std;
const int MaxN = 100, INF = 1000000000;
int N, g[MaxN][MaxN];
int Min(int a, int b)
{
return a < b ? a : b;
}
void floyd()
{
for (int k = 0; k < N; k++)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
g[i][j] = Min(g[i][k] + g[k][j], g[i][j]);
}
}
}
}
int main()
{
N = 5;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i != j)
{
g[i][j] = INF;
}
}
}
g[0][1] = g[1][0] = 3;
g[0][2] = g[2][0] = 2;
g[0][4] = g[4][0] = 12;
g[1][2] = g[2][1] = 6;
g[2][3] = g[3][2] = 5;
g[3][4] = g[4][3] = 4;
floyd();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout<<g[i][j]<<" ";
}
cout<<endl;
}
return 0;
} 运行结果如图： 
拼多多集团-PDD工作强度 285人发布
查看16道真题和解析
