shortestpath.cpp

演示了最短路径的算法逻辑

// ShortestPath.cpp: implementation of the ShortestPath class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "ShortPath.h"
#include "ShortestPath.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

ShortestPath::ShortestPath()
{
	vexnum = 8;
	arcnum = 15;
	//InFo arcinfo;
	int i = 0;
	//插入文件操作
	int f = 0;
	ifstream infile("ShortPath.dat",ios::binary);
	if(!infile)
	{	cerr<<"2cd open file error!";
		exit(1);
	}
	InFo infoout;
	do
	{	infile.read((char *)&infoout,sizeof(InFo));
		if(!infile.eof())
		{		
			info[f].x = infoout.x;
			info[f].y = infoout.y;
			info[f].weight = infoout.weight;
			f++;
		}
	}while(!infile.eof());
	cout<<endl;
	infile.close();
	//
	for(;i < N;i++)
		for(int j = 0;j < N;j++)	
			arcs[i][j] = MAX;

	for(i = 0;i < ARCN;i++)
		arcs[info[i].x][info[i].y] = info[i].weight;

	for(int k = 0;k < N; k++)
		vexs[k] = k + '0';

}

ShortestPath::~ShortestPath()
{

}


void ShortestPath::floyd()
{
	char dd[] = "01234567";
	int i , j , k , n ;
	n = vexnum;
	for(i = 0; i < n; i++)// 预处理path[][]
		for(j = 0;j < N;j++)
		{
			path[i][j].totalweight = arcs[i][j];
			if(path[i][j].totalweight < MAX)
			{
				path[i][j].vex[0] = dd[i];
				path[i][j].vex[1] = dd[j];
				path[i][j].vex[2] = '\0';
			}
			else
				path[i][j].vex[0] = '\0';
		}

	for( k = 0; k < n;k++) // 算法核心，通过尝试插入k来试探出最短路径
		for(i = 0; i < n;i++)
			for(j = 0;j < n;j++)
				if(k != i && k != j && i != j && path[i][k].totalweight + path[k][j].totalweight < path[i][j].totalweight)
				{
					path[i][j].totalweight = path[i][k].totalweight + path[k][j].totalweight;
					strcpy(path[i][j].vex , path[i][k].vex);
					strcat(path[i][j].vex , path[k][j].vex+1);
				}
}

/*bool ShortestPath::find_f_e(char from,char end)
{
	int i = 0;
	for(; i < N ;i++)
		if(vexs[i] == from)
			break;
	if(i == N)
		return false;

	for(i = 0;i < N;i++)
		if(vexs[i] == end)
			break;
	if(i == N)
		return false;

	return true;
}*/

int ShortestPath::get_shortpath(char from,char end,string& sshort)
{
	int k = 0;
	sshort = "";
	int i = 0;
	int j = 0;

	for(; i < N ;i++)	//查找from在vexs[]中的位置，判断from的合法性
	{
		if(vexs[i] == from)
		{break;}
	}
	if(i == N)
	{	return 0;}	//finished

	for(j = 0;j < N;j++)	//查找end在vexs[]中的位置，判断end的合法性
	{
		if(vexs[j] == end)
			break;
	}
	if(j == N)
	{return 0;}		//finished}

	//return true;

	for(; path[i][j].vex[k] != '\0';k++)
		sshort += path[i][j].vex[k];

	sshort += '\0';

	//if(sshort.empty() == 0)
		//return false;

	return k;
}