shortestpath.cpp

最短路问题的求解 最短路问题的求解

// ShortestPath.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "string.h"
#define  LENGTH 20 
#include "iostream.h"

void findPath(int v1,int v2,int  **point,int length,int lengthPath,int step,int *vector)
{ 	
	int **p; 
	int rememberLength=lengthPath;
	p=point;
	if(step>length)
	{
      printf("次路不通\n");
	  return;
	}
	if(v1==v2)
	{	  
		for(int n=0;n<step;n++)
		{
	 	printf("%d",vector[n]);
		}
	    printf("总路长：%d\n",lengthPath); 
	   return;
	}
	point[v1][v1]=0; 
	for(int i=0;i<length;i++)
	{
		if(i!=v1)
		{
	        if(point[v1][i]>0)
			{  	
				bool key=true;
				for(int m=0;m<step;m++)
				{
					if(vector[m]==i)
					{
						key=false;
					    break;
					}
				}
				if(key)
				{
				 printf("%d--(%d)-->%d  ",v1, p[v1][i],i); 
				 vector[step-1]=v1;	
				 vector[step]=i;
				 lengthPath+=p[v1][i];			 
			     findPath(i,v2,p,length,lengthPath,++step,vector); 
				 step--;
				}
			}	
			lengthPath=rememberLength;
		}		
	}
}
int main(int argc, char* argv[])
{
	//////// 创建邻接矩阵 
	int lengthRow=0,length=0;	
	int v1;
    int v2;
	char points[LENGTH];
	long lengthPath=0; 
	FILE *fp;
	fp=fopen("path.txt","r");
	while(!feof(fp))
	{
		fscanf(fp,"%s",&points); 	 
	    length++;
	}  
	int **point=new int*[length]; 
	int *vector=new int[length];
	for(int i=0;i<length;i++)
	{
	 point[i]=new int[length];
	}  
	///// 存储所有的点
	fp=fopen("path.txt","r");
	while(!feof(fp))
	{
		int sum=0,m=0,k=0,s=1;
	  fscanf(fp,"%s",&points); 
	   length=0;
      points[strlen(points)]='\0';
	  for(int j=0;j<strlen(points);j++)
	  {
	      if(points[j]==',')
		  {
		    for(m=j-1;m>=k;m--)
			{
				if(points[m]=='-')
				{
				 sum=-1;
				 break;
				}
				if(points[m]!=' ')
				{
			       sum=sum+(int)(points[m]-48)*s;
			       s=s*10;
				}
			}
			point[lengthRow][length]=sum;
			s=1;
			sum=0;
			k=j+1;
			length++;
		  }	
	  }	 
		  lengthRow++;
	} 
	printf("  ");
	for(int q=0;q<length;q++)
	{
	 printf("  V%d",q);
	}
	 printf("\n");
	for(int m=0;m<length;m++)
	{
    	printf("V%d ",m);
	  for(int n=0;n<length;n++)
	  {
	     printf("%d  ",point[m][n]);
	  }
	    printf("\n");
	}
	printf("请输入你当前的位置！\n");    
	scanf("%d",&v1); 
 	printf("请输入你要到达的目的地！\n");	   
	scanf("%d",&v2);
    findPath(v1,v2,point,length,lengthPath,1,vector);//查找最短路径	 	 
	printf("\n");
	return 0;
}