弗洛伊德算法

弗洛伊德算法的原理是动态规划

设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;
}

运行结果如图：