main.h

Dijkstrat和Floyd算法实现。 算法请参考《通信网理论基础》周炯磐

#define MAX_POINTNUM 20
#define POINTNUM 6
#define GrobalG GrobalG1
#define MAX_WEIGHT 10000000
double GrobalG1[MAX_POINTNUM][MAX_POINTNUM]=
{
	{0,	9,	1,	3,	MAX_WEIGHT,	MAX_WEIGHT},
	{1,	0,	4,	MAX_WEIGHT,	7,	MAX_WEIGHT},
	{2,	MAX_WEIGHT,	0,	MAX_WEIGHT,	1,	MAX_WEIGHT},
	{MAX_WEIGHT,	MAX_WEIGHT,	5,	0,	2,	7},
	{MAX_WEIGHT,	6,	2,	8,	0,	5},
	{7,	MAX_WEIGHT,	2,	MAX_WEIGHT,	2,	0}
};
double GrobalG2[MAX_POINTNUM][MAX_POINTNUM]=
{
	{0,MAX_WEIGHT,MAX_WEIGHT,1.2,9.2,MAX_WEIGHT,0.5},
	{MAX_WEIGHT,0,MAX_WEIGHT,5,MAX_WEIGHT,3.1,2},
	{MAX_WEIGHT,MAX_WEIGHT,0,MAX_WEIGHT,MAX_WEIGHT,4,1.5},
	{1.2,5,MAX_WEIGHT,0,6.7,MAX_WEIGHT,MAX_WEIGHT},
	{9.2,MAX_WEIGHT,MAX_WEIGHT,6.7,0,15.6,MAX_WEIGHT},
	{MAX_WEIGHT,3.1,4,MAX_WEIGHT,15.6,0,MAX_WEIGHT},
	{0.5,2,1.5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0}
};
class Graph
{
public:
	int unsigned pointNum;
	double graph[MAX_POINTNUM][MAX_POINTNUM];
public:
	Graph();
	Graph(int unsigned num,const double (*gr)[MAX_POINTNUM]);
};
Graph::Graph()
{}

Graph::Graph(int unsigned num,const double (*gr)[MAX_POINTNUM])
{
	pointNum=num;
	unsigned int i,j;
	for(i=0;i<num;i++)
		for(j=0;j<num;j++)
			graph[i][j]=gr[i][j];
}
struct DijkstraData
{
	int WeightPriorityPoint[MAX_POINTNUM];
	int FatherPoint[MAX_POINTNUM];
};

class DijkstraFloyd
{
private:
	//	int pointNum;
	Graph g;
	/*********************
	Graph DijkstraGraph;
	Graph FloydGraph;
	**********************/
public:
	DijkstraFloyd(int unsigned num, double (*gr)[MAX_POINTNUM]);
public:
	bool Dijkstra(int unsigned pointPosition, DijkstraData& DiDa);
	void PrintDijkstra(const int unsigned pointPosition);
	void GetPointToPointRoad(int PointBegin, int PointEnd, int Road[]);
	void FloydGetPointToPointRoad(unsigned PointBegin, unsigned PointEnd, int Road[]);
	void Floyd(Graph& Weight, Graph& Relation);
	int CenterPoint(Graph graph);
	int AverageCenterPoint(Graph graph);
};


DijkstraFloyd::DijkstraFloyd(int unsigned num, double (*gr)[MAX_POINTNUM]):g(num, gr)
{
	
}

bool DijkstraFloyd::Dijkstra(int unsigned pointPosition, DijkstraData& DiDa)
/*Dijkstra算法：
给定图G，求指定端点pointPosition到其它端点的最短径。
D算法把端集分为两组，一组称为端集Gp，另一组为G-Gp。
pointPosition为其中一端点
Di[0][i]指定Dijkstra最短径长的顺序
Di[1][i]指定其最短树的父端点
*/
{
	if(pointPosition>=g.pointNum)false;
	
	
	int unsigned i,j,k;
	int unsigned PointPriority,PointRemain,PointPrioritySave,PointRemainSave;
	double Weight;
	double WeightSave[POINTNUM];
	i=g.pointNum;
	while(i--)
	{
		WeightSave[i]=0;
		DiDa.FatherPoint[i]=0;
		DiDa.WeightPriorityPoint[i]=i;
	}
	DiDa.WeightPriorityPoint[0]=pointPosition;
	DiDa.WeightPriorityPoint[pointPosition]=0;
	DiDa.FatherPoint[pointPosition]=pointPosition;
	for(i=0; i<g.pointNum-1; i++)
	{
		Weight=MAX_WEIGHT;
		for(j=0; j<=i; j++)//Gp
		{
			PointPriority=DiDa.WeightPriorityPoint[j];
			for(k=i+1; k<g.pointNum; k++)//G-Gp
			{					
				PointRemain=DiDa.WeightPriorityPoint[k];
				if(Weight>g.graph[PointPriority][PointRemain]+WeightSave[PointPriority])
				{
					Weight=g.graph[PointPriority][PointRemain]+WeightSave[PointPriority];
					PointPrioritySave=PointPriority;
					PointRemainSave=PointRemain;
				}
			}
			
		}
		if(Weight==MAX_WEIGHT)
			cout<<"Remainer Untachable!\n";
		else
		{
			WeightSave[PointRemainSave]=Weight;
			DiDa.FatherPoint[PointRemainSave]=PointPrioritySave;
		}
		for(k=i+1; k<g.pointNum; k++)if(PointRemainSave==k)
		{
			DiDa.WeightPriorityPoint[k]=DiDa.WeightPriorityPoint[i+1];
			DiDa.WeightPriorityPoint[i+1]=k;
			break;
		}
	}
	return true;
}
void DijkstraFloyd::PrintDijkstra(const int unsigned pointPosition)
{
	double Gp[MAX_POINTNUM][MAX_POINTNUM];
	int priorityson,priorityfather;
	DijkstraData DiDa;
	Dijkstra(pointPosition,DiDa);
	unsigned int Temp[MAX_POINTNUM];
	unsigned int i,j;
	for (i=0;i<g.pointNum;i++)Temp[i]=0;
	for (i=0;i<g.pointNum;i++)
	{	
		priorityson=DiDa.WeightPriorityPoint[i];
		priorityfather=DiDa.FatherPoint[i];
		Gp[priorityson][Temp[priorityfather]]=priorityfather;		
		for(j=0;j<Temp[DiDa.FatherPoint[i]];j++)Gp[priorityson][j]=Gp[priorityfather][j];		
		for(j=Temp[DiDa.FatherPoint[i]]+1;j<g.pointNum;j++)Gp[priorityson][j]=0;
		Temp[DiDa.WeightPriorityPoint[i]]=Temp[DiDa.FatherPoint[i]]+1;
	}
	for (i=0; i<g.pointNum; i++)
	{
		for (j=0; j<g.pointNum; j++)
			cout<<Gp[i][j]<<"\t";
		cout<<endl;
	}
}

/****************************************
if Road[0]==-1 input error
if Road[0]==-2 dijkstra() error
****************************************/
void DijkstraFloyd::GetPointToPointRoad(int PointBegin, int PointEnd, int Road[])
{
	if(unsigned(PointEnd)>=g.pointNum)
	{
		Road[0]=-1;
		return;
	}
	DijkstraData DiDa;
	Dijkstra(PointBegin,DiDa);
	int FatherPoint=PointEnd;
	for(unsigned int i=0; i<g.pointNum; i++)
	{
		
		if((FatherPoint=DiDa.FatherPoint[FatherPoint])==PointBegin)
		{
			Road[0]=i;
			break;
		}
		if(i==g.pointNum-1)
		{
			Road[0]=-1;
			return;
		}
		Road[i+1]=FatherPoint;
	}
}

void DijkstraFloyd::Floyd(Graph& Weight, Graph& Relation)
{
	unsigned int i,j,k;
	for(i=0;i<g.pointNum;i++)
	{
		for (j=0;j<g.pointNum;j++)
		{
			Weight.graph[i][j]=g.graph[i][j];
			if((Weight.graph[i][j]<MAX_WEIGHT)&&(i!=j))
				Relation.graph[i][j]=j;
			else
				Relation.graph[i][j]=0;
		}
	}
	for (k=0;k<g.pointNum;k++)
	{
		for(i=0;i<g.pointNum;i++)
		{
			for (j=0;j<g.pointNum;j++)
			{
				//MinWeight=Weight.graph[i][j];
				
				if(Weight.graph[i][j]>Weight.graph[i][k]+Weight.graph[k][j])
				{
					Weight.graph[i][j]=Weight.graph[i][k]+Weight.graph[k][j];
					Relation.graph[i][j]=k;
				}
			}
			
		}
	}
}

void DijkstraFloyd::FloydGetPointToPointRoad(unsigned PointBegin, unsigned PointEnd, int Road[])
{
	if((PointBegin>=g.pointNum)||(PointEnd>=g.pointNum))return;
	Graph Weight,Relation;
	Floyd(Weight,Relation);
	Road[0]=0;
	for(unsigned i=0; i<g.pointNum-1; i++)
	{
		if(i==g.pointNum-1)
		{
			cout<<"error FloydGetPointToPointRoad!\n";
			break;
		}
		if(PointEnd!=(unsigned)Relation.graph[PointBegin][PointEnd])
		{
			Road[0]++;
			Road[i+1]=PointEnd;
			PointEnd=(unsigned)Relation.graph[PointBegin][PointEnd];			
		}
	}
}