学步园

其实我觉得这个算法还是很简单的，但是看网上的资料感觉很高深，说的我稀里糊涂的。难道是我想错啦？希望大神帮我指正（真心没自信）。。谢谢。

/*
Floyd算法：可以解决任何两点间的最短距离问题。而dijkstra算法是解决源节点和目的节点两个之间的最短距离问题。
Floyd算法思想: 如果两点的最短距离不是两点的带权路径的权值，而是通过中间的某个节点或多个节点才有了这个最短路径。所以我们对于任何两个节点的最短路径问题可以这么考虑：其他节点和这个最短路径只有两种关系:在这个最短路径序列中和不在这个最短路径序列中。假如有V0--Vn这么多个节点，那么任意两个节点Vi和Vj，分别考虑当插入V0--Vn后Vi和Vj的距离。当插入所有的节点后，任何两个节点的最短路径就求出来了，复杂度为O(n^3);
*/

#include<iostream>
using namespace std;

#define MAX 1024

int D[MAX][MAX];//记录任何两个节点的距离
int A=0;

void findThePath(int nodes)
{
	int i,j,k;
	for(i=1;i<nodes;i++)
	{
		for(j=0;j<nodes;j++)
		{
			if(j!=A)
			{
				for(k=j+1;k<nodes;k++)
				{
					if((j!=k)&&D[j][k]>D[j][i]+D[i][k])
					{
						D[j][k]=D[j][i]+D[i][k];
						D[k][j]=D[j][k];
					}
				}
			}
		}
		A++;
	}
}

void main()
{
	int nodes,edges;
	int firstnode,secondnode,dis;
	int i,j;
	while(1)
	{
		cin>>nodes>>edges;
		for(i=0;i<nodes;i++)
			for(j=0;j<nodes;j++)
			{
				if(i==j)
					D[i][j]=0;
				else
					D[i][j]=MAX;		
			}
		for(i=0;i<edges;i++)
		{
			cin>>firstnode>>secondnode>>dis;
			D[firstnode][secondnode]=dis;
			D[secondnode][firstnode]=dis;
		}
		findThePath(nodes);

		cout<<"0和3的最小路径:	"<<D[0][3]<<endl;
		cout<<"1和2的最小路径:	"<<D[1][2]<<endl;
		cout<<"2和3的最小路径:	"<<D[2][3]<<endl;
		cout<<"1和3的最小路径:	"<<D[1][3]<<endl;
		cout<<"0和1的最小路径:	"<<D[0][1]<<endl;
	}
}