shortpath.cpp

实现了图的数据结构和Dijkstra算法。例子为中关村附近的交通问题。

///////////////////////////////////////////////////////////////////////
//					无向图中两点间最短路径的查找					 //
///////////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <string.h>
#include <malloc.h>

//-------------------图的数组（邻接矩阵）存储表示----------------------

#define MAX_VEX_NUM 20
#define MAX_NAME_STR 20
#define INFINITY 65535
#define TRUE 1
#define FALSE 0

//每个边的数据结构
typedef struct ArcCell
{
	unsigned int length;			//长度
	float rate;						//比例
	unsigned int weight;			//加权长度，即考虑堵车因子后的实际长度（与通过时间成正比）
}ArcCell,AdjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];

class Graph
{
//数据：
	char *vex[MAX_VEX_NUM];			//顶点向量，每顶对应一地名字串
	AdjMatrix arcs;					//邻接矩阵，（即边的关系矩阵）
	int vexnum,arcnum;				//顶数和边数
public:


//成员函数：
Graph()								//构造函数
{
	int i,j;

	for(i=0;i<vexnum;i++)
		for(j=0;j<vexnum;j++)
		{
			if(i!=j)				//不同顶间置为无限
			{
				arcs[i][j].weight=INFINITY;
				arcs[j][i].weight=INFINITY;
			}
			else arcs[i][j].weight=0;	//同顶置零
		}

	//初值均为零
	vexnum=0;
	arcnum=0;
}

void AddVex(char *s)
//添加一个顶,地名为参数
{
	if(vexnum>=MAX_VEX_NUM-1)
	{
		cout<<"顶点数已达上限，不可再加！"<<endl;
		return;
	}
	else
	{
		vex[vexnum]=(char*)malloc(sizeof(char)*MAX_NAME_STR);		//为地名串开辟空间
		strcpy(vex[vexnum],s);										//复制
		vexnum++;
	//output:
		cout<<"第"<<vexnum<<"顶:"<<vex[vexnum-1]<<"已被添加。"<<endl;
	}
}

void AddArc(int i,int j,unsigned int len,float r=1.0)
//添加一条边，两顶，长度和比例为参数
{
	if(i<0||i>vexnum-1||j<0||j>vexnum-1)
	{
		cout<<"插入边超出已有顶的范围！"<<endl;
		return;
	}
	else
	{
		arcs[i][j].length=len;
		arcs[i][j].rate=r;
		arcs[i][j].weight=(int)(len*r);
		arcs[j][i].length=len;
		arcs[j][i].rate=r;
		arcs[j][i].weight=(int)(len*r);
		arcnum++;
	//output:
		cout<<"新边 "<<vex[i]<<"<-->"<<vex[j]<<" 被加入:";
		cout<<"长度:"<<len<<",堵车延迟率:"<<r<<",加权长度:"<<len*r<<"。"<<endl;
	}
}

bool IsArc(int i,int j)
//判断两点间有无边相连
{
	if(arcs[i][j].weight<INFINITY)return 1;
	else return 0;
}

void ShortestPath_DIJ(int v0,int vp)
//求v0到vp的最短路径（Dijkstra）
{
	bool P[MAX_VEX_NUM][MAX_VEX_NUM];		//路径矩阵
	unsigned int D[MAX_VEX_NUM];			//路径长度向量
	bool final[MAX_VEX_NUM];

	int v,w;
	for(v=0;v<vexnum;v++)
	{
		final[v]=FALSE;
		D[v]=arcs[v0][v].weight;
		for(w=0;w<vexnum;w++)P[v][w]=FALSE;		//设空路径
		if(D[v]<INFINITY)
		{
			P[v][v0]=TRUE;
			P[v][v]=TRUE;
		}
	}

	D[v0]=0;
	final[v0]=TRUE;								//初始化，v0顶点属于S集
	
	//开始主循环，每次求得v0到某个v的的最短路径，加v到S集
	int i,j;
	unsigned int min;

	for(i=1;i<vexnum;i++)						//其余vexnum-1个顶
	{

	//output:
	//	for(j=0;j<vexnum;j++)cout<<D[j]<<",";
	//	cout<<endl;

		min=INFINITY;							//当前所知离v0顶最近距离
		for(w=0;w<vexnum;w++)
			if(!final[w])						//w在V-S中
				if(D[w]<min)					//w更近
				{
					v=w;
					min=D[w];
				}
		final[v]=TRUE;
		for(w=0;w<vexnum;w++)					//更新路径
			if(!final[w]&&((min+arcs[v][w].weight)<D[w]))
			{
				D[w]=min+arcs[v][w].weight;
				for(j=0;j<vexnum;j++)P[w][j]=P[v][j];
				P[w][w]=TRUE;
			}
	}

//output:（输出目标路径）
	int lucy=v0;

	cout<<"目标路径为:"<<endl;
	for(j=0;j<vexnum;j++)cout<<P[vp][j];
	cout<<endl;

	while(lucy!=vp)
	{
		cout<<vex[lucy]<<"-->";
		min=INFINITY;
		for(i=0;i<vexnum;i++)
		{			
			if((P[vp][i]==TRUE)&&(lucy!=i))
			{
				if(arcs[lucy][i].weight<min)
				{
					min=arcs[lucy][i].weight;
					j=i;					
				}
			}
		}
		lucy=j;
		P[vp][j]=FALSE;
	}
	cout<<vex[vp]<<endl;
}

virtual ~Graph()
{
	while(--vexnum>0)delete vex[vexnum];
}
};


///////////////////////////////主函数/////////////////////////////
void main()
{
	Graph g;

	g.AddVex("动物园");
	g.AddVex("中关村");
	g.AddVex("清华园");
	g.AddVex("圆明园");
	g.AddVex("二里庄");
	g.AddVex("西直门");
	g.AddVex("牡丹园");
	g.AddVex("新街口");
	g.AddVex("小西天");
	g.AddVex("太平庄");
	g.AddVex("亚运村");
	
	g.AddArc(0,1,8);
	g.AddArc(1,2,3);
	g.AddArc(1,5,8);
	g.AddArc(2,4,7);
	g.AddArc(2,6,8);
	g.AddArc(3,4,5);
	g.AddArc(4,6,6);
	g.AddArc(4,5,4);
	g.AddArc(4,10,6);
	g.AddArc(5,6,6);
	g.AddArc(5,7,3);
	g.AddArc(5,8,7);
	g.AddArc(6,9,5);
	g.AddArc(8,9,6);
	g.AddArc(9,10,7);

	g.ShortestPath_DIJ(4,0);
}