pathfunction.cpp

算法实验:1 分治法在数值问题中的应用 ——最近点对问题 2 减治法在组合问题中的应用——8枚硬币问题 3 变治法在排序问题中的应用——堆排序 4 动态规划法在图问题中的应用——全源最短路径问题

#include "shortestPath.h"

//get the location of v0 in the DNetwork
//return -1 if v0 is not exist
int VexLocation(DNetwork G,VertexType v0){
	assert( strlen(v0)!=0 );
	int i;
	for(i=0;i<G.vexnum;i++){
		if( strcmp(G.vexs[i],v0)==0 )
			return i;
	}
	return -1;
}

//Output the infomation
void OutputDN(DNetwork G){
	assert( strlen(G.vexs[0])!=0 );
	int i,j;
	printf("DNetwork's vertexs:\n");
	for(i=0;i<G.vexnum;i++){
		printf("%-5s",G.vexs[i]);
	}
	puts("\nDNetwork's arcs:\n");
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]<INFINITY)
				printf("<%s,%s>  %d\n",G.vexs[i],G.vexs[j],G.arcs[i][j]);
		}
	}//for(i=0)
	printf("\n");
}



//create a Dignetwork,get the infomations from file
void CreateDN(DNetwork *G,const char vexinfo[],const char arcinfo[]){
	assert(strlen(vexinfo)!=0);
	(*G).vexnum=0;
	(*G).arcnum=0;
	int i,j;
	char c[MAX_NAME], c1[MAX_NAME],weight[MAX_NAME];
	FILE *fp1,*fp2;

	if( (fp1=fopen(vexinfo,"r"))==NULL ){//vextex infomation file
		printf("Can not open the file !!!");
		exit(FILE_OPEN_ERROR);
	}
	while(!feof(fp1)){
		fscanf(fp1,"%s%*c",c);
		strcpy((*G).vexs[(*G).vexnum++],c);
	}
	fclose(fp1);

	for(i=0;i<(*G).vexnum;i++){//initialize Adjaceny Matrix
		for(j=0;j<(*G).vexnum;j++){
			(*G).arcs[i][j]=INFINITY;
		}
	}//for(i=0)

	if( (fp2=fopen(arcinfo,"r"))==NULL ){//arcs infomation file
		printf("Can not open the file !!!");
		exit(FILE_OPEN_ERROR);
	}

	while(!feof(fp2)){
		fscanf(fp2,"%s%s%s",c,c1,weight);
		i=VexLocation(*G,c);
		j=VexLocation(*G,c1);
		if(i!=-1 || j!=-1){
			(*G).arcs[i][j]=atoi(weight);
			(*G).arcnum++;
		}
	}
	fclose(fp2);
}


//==========================================================
/*弗洛伊德算法
typedef struct{
	VertexType path;//顶点类型为A、B、C、D之类
}PthMatrix[MAX_VERTEX][MAX_VERTEX]; //path
typedef int DistancMatrix[MAX_VERTEX][MAX_VERTEX]; //weigth
*==========================================================*/
void ShortestPath_FLOYD(DNetwork G,PthMatrix *P,DistancMatrix *D){
	int i,j,k,len,len1;
	VertexType c="\0";
	for(i=0;i<G.vexnum;i++){//initialize Matrix
		for(j=0;j<G.vexnum;j++){
			if(i==j)	//the value of each diagnoal element is 0
				(*D)[i][j]=0;
			else	(*D)[i][j]=G.arcs[i][j];

			if(G.arcs[i][j]<INFINITY){
				strcpy(c,G.vexs[i]);
				strcat(c,G.vexs[j]);
				strcpy((*P)[i][j].path,c);
			}
			else strcpy((*P)[i][j].path,"∞\0");
		}
	}//for(i=0)

	for(k=0;k<G.vexnum;k++){
		for(i=0;i<G.vexnum;i++){//starting point
			for(j=0;j<G.vexnum;j++){//destination
				if( (*D)[i][k] !=INFINITY && (*D)[k][j]!=INFINITY )//路径存在
					if( (*D)[i][k]+(*D)[k][j]<(*D)[i][j] ){//∞mean no path
						(*D)[i][j]=(*D)[i][k]+(*D)[k][j];
						//printf("%d",(*D)[i][j]);
						VertexType c="\0";
						len=strlen((*P)[i][k].path);
							
						memcpy(c,(*P)[i][k].path,len-1);
						strcat(c,(*P)[k][j].path);
						strcpy((*P)[i][j].path,c);		
					}
			}//for(j=0)
		}//for(i=0)
	}//for(k=0)

}


void PathStart(){
	DNetwork G;
	PthMatrix P;
	DistancMatrix D;
	int i,j,order;
	char c;
begin:
	system("cls");
	printf("选择测试文件(1 顶点.txt,弧.txt  2 顶点1.txt,弧1.txt) ");
	scanf("%d",&order);
	if(order==1)
		CreateDN(&G,"顶点.txt","弧.txt");
	else
		CreateDN(&G,"顶点1.txt","弧1.txt");
	OutputDN(G);
	ShortestPath_FLOYD(G,&P,&D);
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++)
			if( strcmp(P[i][j].path,"∞")!=0 ){
				printf("%s->%s:  ",G.vexs[i],G.vexs[j]);
				printf("%s ",P[i][j].path);
				printf("=%d\n",D[i][j]);
			}
	}//

	printf("继续?(y/n)\n");
	while((c = getchar()) != '\n' && c != EOF);
	if(getchar()=='y')
		goto begin;

}