routing1.cpp

实现最短路径算法。 实现最短路径算法。

				}
				else
					addFlag = true;
			}

			if(addFlag)
			{
				nextArc  = (ArcNode *)malloc(sizeof(ArcNode));
				if(nextArc == 0)
					return false;
				nextArc->arcNo          = arcNo;
				nextArc->info.tailVexNo = desNo;
				memcpy(currArc->info.arcName,arcName,MAXNAME);
				memset(nextArc->info.roadName,'\0',MAXNAME);
				nextArc->info.distance   = MAXCOST;
				nextArc->info.time       = MAXCOST;
				nextArc->nextArc         = 0;
				//
				if(!(currVex->firstArc))
					currVex->firstArc = nextArc;
				else
					currArc->nextArc = nextArc;
			}
			currVex = *graph;
			while(currVex->vexNo != desNo && currVex->nextVex)
				currVex = currVex->nextVex;
			if(currVex->vexNo != desNo)
				return false;
			for(i=0;i<MAXARCNUM;i++)//pay attention to it
			{
				if(fscanf(topoFp,"%d",&arcNo) == 1 && arcNo >0)
				{
					addFlag = false;
					currArc = currVex->firstArc;
					if(!currArc)
						addFlag = true;
					else
					{
						while(currArc->nextArc && currArc->arcNo != arcNo)
							currArc = currArc->nextArc;
						if(currArc->arcNo == arcNo)
							currArc->arcNo   = arcNo;
						else
							addFlag = true;
					}

					if(addFlag)
					{
						nextArc  = (ArcNode *)malloc(sizeof(ArcNode));
						if(nextArc == 0)
							return false;
						nextArc->arcNo          = arcNo;
						nextArc->info.tailVexNo = NOVERTEX;
						memset(nextArc->info.arcName,'\0',MAXNAME);
						memset(nextArc->info.roadName,'\0',MAXNAME);
						nextArc->info.distance   = MAXCOST;
						nextArc->info.time       = MAXCOST;
						nextArc->nextArc         = 0;
						if(!(currVex->firstArc))
						{
							currVex->firstArc = nextArc;
							currArc = nextArc;
						}
						else
							currArc->nextArc = nextArc;
					}
				}
			}
		}
		else
			return false;
	}
	return true;
}
//////////////////////////////////////////////////////////////////
//set the distance and time attribute 
/////////////////////////////////////////////////////////////////
bool Set_Attr(FILE *attrFp,VexNode **graph)
{
	bool     findFlag;//
	int      arcNo;
	char     arcName[MAXNAME],roadName[MAXNAME];
	double   tim,dis;
	VexNode  *currVex;
	ArcNode  *currArc;
	while(!feof(attrFp))
	{
		memset(arcName,'\0',MAXNAME);
		memset(roadName,'\0',MAXNAME);
		if(fscanf(attrFp,"%d %s %lf %lf %s",&arcNo,arcName,&dis,&tim,roadName) == 5)
		{
			currVex = *graph;
			findFlag = false;
			while(currVex && !findFlag)
			{
				currArc = currVex->firstArc;
				if(currArc)
				{
					while(currArc->arcNo != arcNo && currArc->nextArc)
						currArc = currArc->nextArc;
					if(currArc->arcNo == arcNo)
					{
						memcpy(currArc->info.arcName,arcName,MAXNAME);
						memcpy(currArc->info.roadName,roadName,MAXNAME);
						currArc->info.distance = dis;
						currArc->info.time     = dis/tim;
						findFlag = true;
					}
				}
				currVex = currVex->nextVex;
			}
			if(!findFlag)
				return false;
		}
		else
			return false;
	}
	return true;
}
//////////////////////////////////////////////////////////////////
//complement the graph
/////////////////////////////////////////////////////////////////
bool complement(VexNode **graph)
{
	int      arcNo,souNo,desNo;
	VexNode  *currVex,*nextVex;
	ArcNode  *currArc,*nextArc;
	currVex = *graph;
	while( currVex )
	{
		if( currVex->firstArc )
		{
			souNo  = currVex->vexNo;
			currArc = currVex->firstArc;
			while(currArc)
			{
				desNo  = currArc->info.tailVexNo;
				if(desNo == NOVERTEX)
				{
					arcNo  = currArc->arcNo;
					nextVex = *graph;
					while(nextVex)
					{
						if(nextVex != currVex && nextVex->vexNo == souNo && nextVex->firstArc)
						{
							nextArc = nextVex->firstArc;
							while(nextArc->nextArc && (nextArc->arcNo != arcNo || nextArc->info.tailVexNo == NOVERTEX))
								nextArc = nextArc->nextArc;
							if(nextArc->arcNo == arcNo && nextArc->info.tailVexNo != NOVERTEX)
								currArc->info.tailVexNo = nextArc->info.tailVexNo;
						}
						nextVex = nextVex->nextVex;
					}
				}
				currArc = currArc->nextArc;
			}
		}
		currVex = currVex->nextVex;
	}
	return true;
}
///////////////////////////////////////////////////////////////
//Dijkstra function
//vertex is numbered from 1...
///////////////////////////////////////////////////////////////
bool graph_Dij(VexNode *graph,int souNo,int desNo,double *allCost,int kind,PathNode **path)
{
	bool existFlag,minFlag;
	int vexNo,arcNo;    //vex No.
	int vexNum;    //vex Number
	int i,j,k;     
	int    *pSet;   //store the final vertex of shortest paths that found
	int    *pathV;  //store the fore vertex of the vertex in the shortest path
	int    *pathA;  //store the arc link to the vertex in the shortest path
	double *cost;   //store the cost of the shortest path
	VexNode *currVex;
	ArcNode *currArc;
	PathNode *currPath,*nextPath;

	//get vertex number
	vexNum = 0;
	currVex = graph;
	while(currVex)
	{
		vexNum++;
		currVex = currVex->nextVex;
	}
	if(souNo<1 || souNo>vexNum || desNo<1 || desNo>vexNum)
		return false;
	pSet  = (int *)malloc(sizeof(int)*vexNum );
	pathV  = (int *)malloc(sizeof(int)*vexNum );
	pathA = (int *)malloc(sizeof(int)*vexNum );
	cost  = (double *)malloc(sizeof(double)*vexNum );
	if(!pSet || !pathV || !cost || !pathA)
		return false;
	//initialize
	for(i=0;i<vexNum;i++)
	{
		pSet[i]  = NOVERTEX;
		pathV[i]  = NOVERTEX;
		pathA[i] = NOARC;
		cost[i]  = MAXCOST;
	}
	currVex = graph;
	while(currVex)
	{
		if(currVex->vexNo == souNo)
		{
			currArc = currVex->firstArc;
			while(currArc)
			{
				if(kind == DISTANCE)
					cost[currArc->info.tailVexNo-1]  = currArc->info.distance;
				else if(kind == TIME)
					cost[currArc->info.tailVexNo-1]  = currArc->info.time;
				pathV[currArc->info.tailVexNo-1] = currVex->vexNo;
				pathA[currArc->info.tailVexNo-1] = currArc->arcNo;
				currArc = currArc->nextArc;

			}
		}
		currVex = currVex->nextVex;
	}
	//get shortest path
	existFlag = false;
	pSet[0]     = souNo;
	for( i = 1; i < vexNum; i++)
	{
		//
		bool   inFlag;
		int    minNo;
		double minCost = MAXCOST;
		minFlag = false;
		//find the shortest path's final vertex
		for(j=0;j< vexNum; j++)
		{
			inFlag = false;
			for( k = 1; k < i; k++)
			{
				if(pSet[k] == j+1)
				{
					inFlag = true;
					break;
				}
				if(pSet[k] == NOVERTEX)
				{
					break;
				}
			}
			if(inFlag)
				continue;
			if(cost[j] < minCost)
			{
				minCost = cost[j];
				minNo = j+1;
				minFlag = true;
			}
		}
		if(minFlag == false)
		{
			existFlag = false;
			break;// go out the loop
		}
		pSet[i]       = minNo;
		cost[minNo-1] = minCost;
		if(minNo == desNo)
		{
			existFlag = true;
			break;//go out the loop
		}
		//change the cost linked with this vertex
		currVex = graph;
		while(currVex->nextVex && currVex->vexNo != minNo)
			currVex = currVex->nextVex;
		if(currVex->vexNo == minNo)
		{
			currArc = currVex->firstArc;
			while(currArc )
			{
				if(kind == DISTANCE)
				{
					if(currArc->info.distance + minCost < cost[currArc->info.tailVexNo-1])
					{
						cost[currArc->info.tailVexNo-1]  = currArc->info.distance + minCost;
						pathV[currArc->info.tailVexNo-1] = minNo;
						pathA[currArc->info.tailVexNo-1] = currArc->arcNo;
					}
				}
				else if(kind == TIME)
				{
					if(currArc->info.time + minCost < cost[currArc->info.tailVexNo-1])
					{
						cost[currArc->info.tailVexNo-1]  = currArc->info.time + minCost;
						pathV[currArc->info.tailVexNo-1] = minNo;
						pathA[currArc->info.tailVexNo-1] = currArc->arcNo;
					}
				}
				currArc = currArc->nextArc;
			}
		}
	}
	if(existFlag)
	{
		nextPath = (PathNode*)malloc(sizeof(PathNode));
		if(nextPath == 0)
			return false;
		nextPath->vexNo = desNo;
		nextPath->arcNo = NOARC;
		currVex = graph;
		while(currVex->nextVex && currVex->vexNo != desNo)
			currVex = currVex->nextVex;
		memcpy(nextPath->vexName,currVex->info.vexName,MAXNAME);
		memset(nextPath->arcName ,'\0',MAXNAME);
		memset(nextPath->roadName ,'\0',MAXNAME);
		nextPath->next = 0;
		for( j = i-1; j>=0; j--)
		{
			vexNo = pathV[nextPath->vexNo-1];
			arcNo = pathA[nextPath->vexNo-1];
			currPath = (PathNode*)malloc(sizeof(PathNode));
			if(currPath == 0)
				return false;
			currPath->vexNo = vexNo;
			currPath->arcNo = arcNo;
			currVex = graph;
			while(currVex->nextVex && currVex->vexNo != vexNo)
				currVex = currVex->nextVex;
			memcpy(currPath->vexName,currVex->info.vexName,MAXNAME);
			currArc = currVex->firstArc;
			while(currArc->nextArc && currArc->arcNo != arcNo)
				currArc = currArc->nextArc;
			memcpy(currPath->arcName,currArc->info.arcName,MAXNAME);
			memcpy(currPath->roadName,currArc->info.roadName,MAXNAME);
			currPath->next = nextPath;
			nextPath = currPath;

			if(currPath->vexNo == souNo)
				break;
		}
		*path = currPath;
		*allCost = cost[desNo-1];
	}
	else
	{
		*path = 0;
		*allCost = MAXCOST;
	}

	free(pSet);
	free(pathV);
	free(pathA);
	free(cost);
	return true;
}
DllExport bool create_test(VexNode **graph,char *vexFile,char *topoFile)
{
	FILE *nodeFp,*lineFp;
	if(!(nodeFp = fopen(vexFile,"r")))
		return false;
	if(!(lineFp = fopen(topoFile,"r")))
		return false;
	int      vexNo,countArc,countVex,arcNum,arcNo,headNo,tailNo;
	char name[MAXNAME];
	double   x,y,v,d;
	VexNode  *currVex,*nextVex;
	ArcNode  *currArc,*nextArc;
	countVex = 0;
	nextVex = 0;
	while(!feof(nodeFp))
	{
		if(fscanf(nodeFp,"%d %lf %lf %d",&vexNo,&x,&y,&arcNum) == 4)
		{
			nextVex  = (VexNode *)malloc(sizeof(VexNode));
			if( nextVex == 0)
				return false;
			nextVex->vexNo  = vexNo;
			nextVex->info.x = x;
			nextVex->info.y = y;
			memset(nextVex->info.vexName,'\0',MAXNAME);
			nextVex->firstArc = 0;
			countArc = 0;
			for( int j=0;j<arcNum;j++)
			{
				if(fscanf(nodeFp,"%d ",&arcNo) == 1)
				{
					nextArc  = (ArcNode *)malloc(sizeof(ArcNode));
					if(nextArc == 0)
						return false;
					if(arcNo > 0)
						nextArc->arcNo  = arcNo;
					else
						nextArc->arcNo  = -arcNo;
					memset(nextArc->info.arcName,'\0',MAXNAME);
					memset(nextArc->info.roadName,'\0',MAXNAME);
					nextArc->info.distance = 0.0;
					nextArc->info.time = 0.0;
					nextArc->info.tailVexNo = NOVERTEX;
					nextArc->nextArc = 0;
					if(countArc == 0)
					{
						nextVex->firstArc = nextArc;
						currArc = nextArc;
					}
					else
					{
						currArc->nextArc = nextArc;
						currArc = nextArc;
					}
					countArc++;
				}
			}
			nextVex->nextVex = 0;
			if(countVex == 0)
			{
				*graph = nextVex;
				currVex = nextVex;
			}
			else
			{
				currVex->nextVex = nextVex;
				currVex = nextVex;
			}
			countVex++;
		}
		else
			return false;
	}
	while(!feof(lineFp))
	{
		if(fscanf(lineFp,"%d %d %d %s %lf %lf %d",&arcNo,&headNo,&tailNo,name,&v,&d,&arcNum) == 7)
		{
			currVex = *graph;
			while(currVex && currVex->vexNo != headNo)
				currVex = currVex->nextVex;
			if(currVex->vexNo == headNo)
			{
				currArc = currVex->firstArc;
				while(currArc && currArc->arcNo != arcNo)
					currArc = currArc->nextArc;
				if(currArc && currArc->info.tailVexNo == NOVERTEX)
				{
					currArc->info.tailVexNo = tailNo;
					memcpy(currArc->info.arcName,name,MAXNAME);
					currArc->info.distance = d;
					currArc->info.time = d/v;
				}
			}
			currVex = *graph;
			while(currVex && currVex->vexNo != tailNo)
				currVex = currVex->nextVex;
			if(currVex->vexNo == tailNo)
			{
				currArc = currVex->firstArc;
				while(currArc && currArc->arcNo != arcNo)
					currArc = currArc->nextArc;
				if(currArc && currArc->info.tailVexNo == NOVERTEX)
				{
					currArc->info.tailVexNo = headNo;
					memcpy(currArc->info.arcName,name,MAXNAME);
					currArc->info.distance = d;
					currArc->info.time = d/v;
				}
			}

			for(int j=0 ;j<arcNum;j++)
			{
				fscanf(lineFp,"%lf %lf ",&x,&y);
			}
		}
		else
			return false;
	}
	return true;
}