基于C++的简单最短路径求法 主要解决起讫点不同的问题

#include<iostream>//输入输出流库
#include<fstream>//文本流
using namespace std;
#define MAX_PLACE 100  //定义图中最大的地点数
#define UNLIMTED 1000  //定义图中限定最大的路径值,无穷

int mapRecord[MAX_PLACE][MAX_PLACE],chooseMark[MAX_PLACE];//路径矩阵，标志路径是否被选择过
int templatePath[MAX_PLACE],shortestPath[MAX_PLACE];//临时路径暂时保存所有可行路径，当前最短路径

int minSum,count,sumDistance;//当前最短路径的总长度，记数量--当前路径中地点总数，路径和
int start,totalNum;  //开始点，总地点数
FILE* filePoint;//文件指针--打开文件
int max_distance=UNLIMTED;

void compare_shortest_path(int begin,int end){//寻路算法，深度优先，带剪枝的回溯法
	int i;
	if(begin==end){//当前起点等于所求终点
		if(sumDistance<minSum){         //当前的路径长<最短路径                                       
			minSum=sumDistance;
			shortestPath[0]=count;
			for(i=0;i<count;i++)
				shortestPath[i+1]=templatePath[i]+1;
		}
		count--;
		return;
	}
	if(sumDistance>=minSum){//未到达终点前，路径和已经大于最短
		count--;
		return;
	}
	if(begin==start&&count!=0){//当前起点 = 寻路起点--->记数不为0，就形成回路了
		count--;
		return;
	}
	for(i=0;i<totalNum;i++){
		if(chooseMark[i]==0){//为0没有被走过
			if(mapRecord[begin][i]!=max_distance){//选择有路径的地点
				sumDistance+=mapRecord[begin][i];//累加距离
				chooseMark[i]=1;//标志选择过
				templatePath[count++]=i;//记录当前所选择路径，templatePath[0]=起点，并计数加1，
				compare_shortest_path(i,end);//以当前所选择的路径为起点，继续向下寻找
				chooseMark[i]=0;//更改选择标志，退回再选
				sumDistance-=mapRecord[begin][i];//在总长度中 - 被回退的的路径，即begin->i的长度
			}
		}
	}
	count--;
}


int main(){
	int i,j,k,chosen=0;
	char filename[50];//储存文件名
	
	printf("----------------------欢迎使用，“寻路高手”软件---------------\n");
	printf("请按照提示格式将数据写入记事本,说明如下:\n");  
	//文档要求
	printf("为所有地点编号,第一行为总地点数n+回车;第二行为起始点序号s+回车;\n");
	printf("地点间距离以矩阵的形式,在第3行到第3+n-1行列出，以“空格”间隔，每行以回车结束；\n");
	printf("对于 行数=列数 或者 没有路径的行列 用0来代替！\n");
	printf("请输入寻路矩阵所在的文件名：(文件名.txt)：");
	scanf("%s",filename);//读文件名
	printf("请选择路径种类： 1--有向	2---无向		:");
	scanf("%d",&chosen);
	filePoint=fopen(filename,"r");//只读方式打开
	printf("地图中的地点总数为:");      
	fscanf(filePoint,"%d,",&totalNum);    //输入顶点数
	printf("%d\n寻路起点为：",totalNum);
	fscanf(filePoint,"%d,",&start);
	printf("V%d\n",start);
	start--;//数组以0开始
	
	printf("地点间权值的对应关系如下，注:同一个点间和没有公共边相连的两点间权值设为0.\n");  
	printf("   ");
	for(j=0;j<totalNum;j++)
		printf(" V%d ",j+1);//第几列
	printf("\n");
	for(j=0;j<totalNum;j++){
		printf(" V%d ",j+1);//第几行
		for(k=0;k<totalNum;k++){
			fscanf(filePoint,"%d ",&mapRecord[k][j]);
			printf(" %d ",mapRecord[k][j]);
		}
		printf("\n");//每结束行----换行
	}
	fclose(filePoint);//关闭文件

	int flag=0;//错误指示标志

	for(j=0;j<totalNum;j++){    //输入的矩阵不符合要求时，重新输入
		for(k=0;k<totalNum;k++){
			if(j==k){
				if(mapRecord[j][k]!=0){
					printf("文档中矩阵第%d行对角线不为0！错误！\n",j+1);
					flag=1;
				}
			}
			if(chosen==2&&mapRecord[j][k]!=mapRecord[k][j]){
				printf("文档矩阵[%d][%d]!=[%d][%d],不符合对称规律!错误！\n",j+1,k+1,k+1,j+1); 
				flag=1;
			}
			if(mapRecord[j][k]<0){
				printf("文档矩阵[%d][%d]小于0！错误！\n",j+1,k+1); 
				flag=1;
			}
			if(mapRecord[j][k]>=max_distance)//针对路径中相应修改无穷的值
				max_distance=mapRecord[j][k]*(totalNum+1);
		}
	}

	if(flag==1){//出现错误，flag被标志为1
		printf("寻路选择：( 1 ) 以上错误不影响其他数据，仍然进行运算，以当前数据选择最短路径;\n");
		printf("	      ( 2 ) 以上错误影响其他数据，会使运算发生错误，重新输入。\n");
		scanf("%d",&flag);
		if(flag==2)
			return 1;
	}

	for(j=0;j<totalNum;j++){   //将矩阵里为0的数重新赋值为最大常量，表示同一个点或两点之间无连接
		for(k=0;k<totalNum;k++){
			if(mapRecord[j][k]==0){
				mapRecord[j][k]=max_distance;
			}
		}
	}

	printf("^^^^^^^^^^^^^^^^^^^^^最佳路径：^^^^^^^^^^^^^^^^^^^^^^\n");
	printf("起点~终点:	路径          最小距离和\n");
	for(i=0;i<totalNum;i++){//每次以i为当前的终点
		if(i!=start){//起点不能做终点
			count=0;//计数为0，当前路径数组里没有存储任何路径
			minSum=max_distance;//最小路径设为无穷
			sumDistance=0;//当前路径数组里没有存储任何路径，累加结果为0
			compare_shortest_path(start,i);//找最短路径
			printf("  V%d~V%d:     V%d->",start+1,i+1,start+1);//必须加1，start+1=起点；i+1=终点
			for(j=1;j<shortestPath[0];j++)//shortestPath[0]=最短路径的长度
				printf("V%d->",shortestPath[j]);
			printf("V%d      minuim total distance = %d\n",i+1,minSum);//终点   最小值
		}
	}
	return 0;
}