www.gusucode.com > VC++求两个线段（城市）最短距离的算法-源码程序 > VC++求两个线段（城市）最短距离的算法-源码程序/code/1.cpp

    //Download by http://www.NewXing.com
#include "stdio.h"
#include "iostream.h"
#include "fstream.h"//输入输出流
#include "stdlib.h"
#define mvnum 100//最大定点数
#define maxint 9999
typedef char vertextype;
typedef int adjmatrix;
struct mgraph
{
 vertextype vexs[mvnum];//顶点数组，假定为 char型
 adjmatrix arcs[mvnum][mvnum];//临街矩阵，假定为int型
};
int d[mvnum][mvnum],p[mvnum][mvnum];
////////////
void createmgraph(mgraph *G)
{//采用邻接矩阵表示法构造无向图G
	int i,j,k,w;
	ifstream graphlist("map.txt",ios::in);//定义一个流对象，并且和文件关联
	for(i=1;i<=25;i++)
    G->vexs[i]=(char)i;
	for(i=1;i<=25;i++)
		for(j=1;j<=25;j++)
			G->arcs[i][j]=maxint;//初始化邻接矩阵		
		for(k=1;k<=30;k++)
		{//从磁盘文件接受数据构造网
		    graphlist>>i;
			graphlist>>j;
			graphlist>>w;		   
			G->arcs[i][j]=w;
			G->arcs[j][i]=G->arcs[i][j];//构造无向网
		}
	
			
		//cout<<"图的存储结构建立完毕！"<<endl;
		graphlist.close();//关闭文件
}
///////////////
void floyd(mgraph *G)
{
	int i,j,k;
	for(i=1;i<=25;i++)//设置路径长度D和路径初值
		for(j=1;j<=25;j++)
		{
			if(G->arcs[i][j]!=maxint)
           p[i][j]=j;
			else
				p[i][j]=0;
			d[i][j]=G->arcs[i][j];
		}
		for(k=1;k<=25;k++)
		{
			for(i=1;i<=25;i++)
				for(j=1;j<=25;j++)
				{
					if (d[i][k]+d[k][j]<d[i][j]) 
					{
						d[i][j]=d[i][k]+d[k][j];
						p[i][j]=p[i][k];
						
					}
				}
		}
}
////////////
void main()
{
 mgraph *G;
int v,w,k;
int xz=1;
G=(mgraph *)malloc(sizeof(mgraph));
cout<<"欢迎进入铁路交通网查询系统."<<endl;
createmgraph(G);
while(xz!=0)
{
  cout<<"*******求城市之间最短路径*******"<<endl;
       cout<<"================================"<<endl;
	   cout<<"请选择：1  查询  0  结束"<<endl;
	   cout<<"================================"<<endl;
	   cin>>xz;
	   cout<<endl;
	   if(xz)
	   {
           floyd(G);
		   cout<<"城市名称及编号如下"<<endl;
		      cout<<" 1 乌鲁木齐   2 哈尔滨  3 呼和浩特  4 长春    5 北京"<<endl;
		      cout<<" 6 沈阳       7 西宁    8 天津      9 大连    10 兰州"<<endl;
		      cout<<" 11 西安      12 郑州   13 徐州     14 成都   15 武汉"<<endl;
		      cout<<" 16 上海      17 昆明   18 贵阳     19 株洲   20 南昌"<<endl;
		      cout<<" 21 福州      22 南宁   23 柳州     24 广州   25 深圳"<<endl;
		 cout<<"请输入源点和终点: "<<endl;
	       cin>>v>>w; 
		  k=p[v][w];//k为起点i的后继顶点
		  if(k==0)
			  cout<<"无路径！"<<endl;
		  else
		  {
			  cout<<"所求最短路径为："<<endl;
			  cout<<v;
			  while(k!=w)
			  {
				  
				  cout<<"->"<<k;
				  k=p[k][w];
			  }
			  cout<<"->"<<w;
			  cout<<"路径长度为："<<d[v][w]<<"公里"<<endl;
		  }
          cout<<endl;
	   }
	   else
		   cout<<"谢谢使用，祝您旅途愉快！"<<endl;

   }
}