最短路径.cpp

是用C语言实现的

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

struct direction
{
	direction *next;
	int n;
};

#define MVNum 50   //最大顶点数
struct city
{
	string name;
	int index;
};
typedef struct
{
    city vexs[MVNum];   //顶点数组，类型假定为char型
    int arcs[MVNum][MVNum];  //邻接矩阵，假定为int型
}MGraph;
MGraph pic;

struct l
{
	int len;
	int ok;
	int bef;
};

int min(l *L,int point);//求所有最短路径的最小值
void print(direction *head);//打印以head为头的链表
void dijkstra(int a,int z,int point);//求a到z的最短路径 
int plus();  //图的生成         
void menu();//界面   
void main()
{
   	int point;  
	int i = 0,j;
	bool turn = false;//初始化的判断 
	int choose;  
	int a,z; //a起点z//终点
	 
aaa:
	 menu();
	 cout<<"请选择： ";
	 cin>>choose;
	 switch(choose)
	 {
     case 1:
         point = plus();
		 cout<<"此交通图已创建成功!按任意键继续...";
		 getchar();getchar();
		 turn = true;
		 goto aaa;
		 break;
	 case 2:
			if (turn == false)
			{
				cout<<"交通图尚未创建成功，请按'1'后，再进行此功能"<<endl;
				cout<<"按任意键返回...";
				getchar();getchar();
				goto aaa;
			}
			else
			{	
				for(i = 0;i < point;i++)
				{
					cout<<pic.vexs[i].index+1<<".--"<<pic.vexs[i].name<<"    ";
					if(i%4 == 0 && i != 0) 
					cout<<endl;
				}
				cout<<endl;
				cout<<"请输入出发地: "<<endl;
				cin>>a;
     			for(i = 0;i < point;i++)
				{
					if( i != a-1)
					{
						cout<<a<<"->"<<i+1<<" :  ";
						dijkstra(a-1,i,point);
					}
				}
					cout<<"按任意键继续...";
					getchar();getchar();
					goto aaa;
					break;
				
			}
	 case 3:
		  if (turn == false)
		  {
			  cout<<"交通图尚未创建成功，请按'1'后，再进行此功能"<<endl;
			  cout<<"按任意键返回...";
			  getchar();getchar();
			  goto aaa;
		  }
	      else
		  {	
			  cout<<"\t ";
			  for(i=1;i<=point;i++)
			  {
				  cout<<i<<" \t";
			  }
				  cout<<endl;
			  
			  for(i=0;i<point;i++)
			  {
				  for(j=0;j<point;j++)
				  {
			      if(j==0) cout<<i+1<<"\t ";
			      cout<<pic.arcs[i][j]<<" \t";
				  }
				  cout<<endl;
			  }
			  for(i = 0;i < point;i++)
			  {
				  cout<<pic.vexs[i].index+1<<".--"<<pic.vexs[i].name<<"    ";
				  if(i%4 == 0 && i != 0) 
				  cout<<endl;
			  }
			  cout<<endl;
		      cout<<"请输入出发地: ";
		      cin>>a;			
		      cout<<"请输入目的地: ";
              cin>>z;
              a--;
              z--;
              dijkstra(a,z,point);
		      cout<<"按任意键继续...";
		      getchar();getchar();
		      goto aaa;
		      break;
		  }
	}
}
int plus()
{   

    cout<<"请输入你要咨询的城市名称:"<<endl;
	int i=1;
	while(1)
	{
		cout<<"请输入: ";
		cin>>pic.vexs[i-1].name;
        pic.vexs[i-1].index = i -1;
		cout<<"是否继续 Y / N  ";
		char yes;
		cin>>yes;
		if(yes == 'N' ||yes == 'n')
		break;
		else if (yes == 'Y' ||yes == 'y')
		i++;
		else 
		{
			cout<<"输入错误!"<<endl;
		}
	}
	
    int point;//城市个数
	point = i;
	
	int j;

	for(i=0;i<point;i++)
		for(j=0;j<point;j++)
			pic.arcs[i][j]=0;
	
	cout<<"请输入城市与城市之间的距离关系..."<<endl;

	for(i = 0;i < point;i++)
	{ cout<<pic.vexs[i].index+1<<".--"<<pic.vexs[i].name<<"    ";
	if(i%4 == 0 && i != 0) {cout<<endl;}
	}

	cout<<endl<<"例如1 2 5-----表示1 2 的路径为5"<<endl;
    

	while(1)
	{	
		int a,b,c;
		cout<<"请输入:";
		cin>>a>>b>>c;
	    if(a==b&&b==c&&c==0) break;
		pic.arcs[a-1][b-1]=c;
		cout<<"是否继续输入 Y / N ";
		char yes;
		cin>>yes;
        if(yes == 'N' || yes == 'n') break;
	}
    
	

  return point;
}

void dijkstra(int a,int z,int point)  
{
     l *L;
	 int i;

	 L=new l [point];
	 for(i=0;i<point;i++)
	 {
		 L[i].len=32767;
		 L[i].ok=1;
		 L[i].bef=i;
	 }
	 L[a].len=0;
     
	 int minpoint;
	 while(L[z].ok)
	 {
		 minpoint = min(L,point);
		 L[minpoint].ok = 0;
	     
		 for(i=0;i<point;i++)
		 {
			 if(pic.arcs[minpoint][i])
			 {
				 
				 if(L[i].len > L[minpoint].len+pic.arcs[minpoint][i])
				 {
					 L[i].len=L[minpoint].len+pic.arcs[minpoint][i];
					 L[i].bef=minpoint;
				 }
					
			 }
		 }
	 }
     
     if( L[z].len < 32767 )
	 {
     cout<<"最短路径:"<<L[z].len<<endl;

     int aa=z;
	 direction *head=NULL;
	 direction *p2;
	 p2=new direction;
	 while(1)
	 {
		 p2->n=aa;
		 p2->next=head;
		 head=p2;
		 if(aa==a) break;
		 p2=new direction;
		 aa=L[aa].bef;
	 }
	 cout<<"路径为: ";
	 print(head);
	 }
	 else
	 {
		 cout<<"没有此路径!"<<endl;
	 }
		 

}

int min(l *L,int point)
{
	int i=0;
	int j=0;
	int minlen=32767;
	for(i=0;i<point;i++)
	{
		if(L[i].len<=minlen&&L[i].ok) {minlen=L[i].len;j=i;}
	}
	return j;
}

void print(direction *head)
{

	while(head)
	{
		cout<<head->n+1<<"->";
		head=head->next;
	}
	cout<<"\b\b  "<<endl;
}

void menu()
{
	system("cls");
    cout<<"	－－－－－－欢迎进入交通咨询系统－－－－－－－"<<endl;
	 cout<<"		1.建立交通图的存储结构"<<endl;
	 cout<<"		2.单源城市最短路径"<<endl;
	 cout<<"		3.任意两城市间最短路径"<<endl;
	 cout<<"		0.退出"<<endl;
}