shortdistance.cpp

或得一个连通图两两之间最短路径的代码

// ShortDistance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
const int I = 0xfffffff;
const int Try[5][5]={
	{0,3,8,I,-4},
	{I,0,I,1,7},
	{I,4,0,I,I},
	{2,I,-5,0,I},
	{I,I,I,6,0},
						};
bool GetShortDistance(IN vector<vector<int>> &sgIn,OUT IN vector<vector<int>> &sgOut)
{
	int nSize = sgIn.size();
	sgOut = sgIn;
	for(int round=0;round<nSize-2;round++)
	{
		vector<vector<int>> sgTmp=sgOut;
		for(int i=0;i<nSize;i++)
		{
			for(int j=0;j<nSize;j++)
			{
				for(int k=0;k<nSize;k++)
				{
					sgOut[i][j]=min(sgOut[i][j],sgTmp[i][k]+sgIn[k][j]);
				}
			}
		}
	}
	return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
	vector<vector<int>> t1(5,vector<int>(5,0)),t2;
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			t1[i][j]=Try[i][j];
		}
	}
	GetShortDistance(t1,t2);
	return 0;
}