floyd算法

/*
证明next[i][j] = k;是错误的例子
Node 0 Position (4,61) nextJump -1 Neighbor [3] goodNeighbor [3]
Node 1 Position (89,19) nextJump 1 Neighbor [4, 2] goodNeighbor [4, 2]
Node 2 Position (88,74) nextJump 2 Neighbor [4, 1] goodNeighbor [4, 1]
Node 3 Position (23,85) nextJump 3 Neighbor [4, 0] goodNeighbor [4, 0]
Node 4 Position (68,59) nextJump 3 Neighbor [2, 1, 3] goodNeighbor [2, 1, 3]
*/
#include "iostream"
#include "vector"
using namespace std;
vector<int> path;

int min(int a,int b)
{
	return a>b?b:a;
}
/*
int cost[10][10]=
{
0,    99,      8,     7,     6,     5,    4,     3,     2,     1,  
99,    0,     99,     8,     7,     6,    5,     4,     3,     2,
8,    99,      0,    99,     8,     7,    6,     5,     4,     3,
7,     8,     99,     0,    99,     8,    7,     6,     5,     4,
6,     7,      8,    99,     0,    99,    8,     7,     6,     5,
5,     6,      7,     8,    99,     0,   99,     8,     7,     6,
4,     5,      6,     7,     8,    99,    0,    99,     8,     7,
3,     4,      5,     6,     7,     8,   99,     0,    99,     8,
2,     3,      4,     5,     6,     7,    8,    99,     0,    99,
1,     2,      3,     4,     5,     6,    7,     8,     99,    0
};*/
int len =0;
int cost[5][5] =
{
	99,7,99,6,88,
	5,99,99,4,99,
	99,99,99,99,8,
	9,5,99,99,7,
	99,99,4,6,99
};
int best[5][5];
int next[5][5];
int nodeCount = 5;
void Floyd()
{
	int i,j,k;
	for(i=0;i<nodeCount;i++)
		for(j=0;j<nodeCount;j++)
		{	
			best[i][j]=cost[i][j];
			next[i][j]= (i == j ? -1:i);
		} 
		
		for(k =0;k<nodeCount;k++)
			for(i=0;i<nodeCount;i++)
				if(i != k)
				{
					for(j=0;j<nodeCount;j++)
					{
						if(j != i && j!= k && best[i][j] > best[i][k]+best[k][j])
						{
							best[i][j] = best[i][k]+best[k][j];
							next[i][j] = next[k][j]; //按照这种方法算出来的是前驱，也就是从i到j的路径中j前边的一个顶点。
							//next[i][j] = next[i][k];
							//next[i][j] = k;
						}
					}
				}				
}

int nextJump(int i,int j)//返回的是节点自身
{
	if(i == j)
		return i;
	else if( next[i][j] == -1)
		return -1;
	else
		return nextJump(i,next[i][j]);
}
/*
利用递归的方法把从i到j的路径打印出来
*/
void printPath(int i,int j)
{
	if(i == j)
		cout<<i<<" ";
	else if(i == -1)
		cout<<"no path";
	else
	{
		printPath(i,next[i][j]);
		cout<<j<<" ";
	}
}
/*
这个里边path里半存放的是从i到j得所有中间节点
*/
void savePath(int i,int j)
{
	if(i == j)
		path.push_back(i);
	else if(i == -1)
		cout<<"no path";
	else
	{
		savePath(i,next[i][j]);
		path.push_back(j);
	}
}
main()
{
	Floyd();
	for(int i=0;i<nodeCount;i++)
	{		
		for(int j=0;j<nodeCount;j++)
		{
			//cout<<nextJump(i,j)<<" ";
			//cout<<next[i][j]<<" ";
			path.clear();
			cout<<"path "<<i<<" => "<<j<<":";
			savePath(i,j);
			if(path.size() > 1)				
				cout<<path.at(1);
			else
				cout <<path.at(0);
			cout<<endl;
		}		
		cout<<endl;
	}
	return 0;
}