实验题目：图的结构建立和最短路径算法。
实验目的：练习图的使用。
实验内容：利用邻接矩阵构造图，并求出某一顶点到其余顶点的最短路径并打印输出。
一、需求分析程序刚开始运行时执行初始化，加载“铁路交通图.txt”文件，完成后显示地图上的各节点和编号；然后出现提示信息“请输入出发城市编号：”对话，输入出发城市编号，Enter键结束。
然后出现提示信息“请输入目标城市编号：”对话，输入目标城市编号，Enter键结束。
然后根据用户的输入计算出最短路径，并打印出来。
然后出现提示信息，是否继续，根据用户的选择结束或继续。
（1）测试数据1 112 1312 5二、概要设计(一) 基本操作（1）读取“铁路交通图.txt”文件，并据此建立铁路交通图；（2）根据输入求最短路径，并打印；（3）提示用户是否继续。
(二)本程序包括（1）主程序模块int main()（2）初始化地图模块BOOL InitGraph(MGraph &Graph,FILE *fp);（3）获取最短路径模块BOOL GetPath(MGraph Graph,VertexType vexs1,VertexType vexs2,Path &Path);（4）获取最短路径节点模块BOOL GetShortestPathPoint(Path ShortestPath,int Count,int &DisNum);（5）打印最短路径模块BOOL PrintShortestPath(MGraph Graph,VertexType vexs1,VertexType vexs2,Path ShortestPath);（三）模块调用图：主程序模块初始化地图模块获取最短路径模块获取最短路径节点模块打印最短路径模块三、详细设计（一）元素类型//定义TURE FASLE 表示函数执行情况#define TRUE 1#define FALSE 0#define BOOL char //函数执行情况返回值TRUE成功FLASE失败typedef struct{int Num;//顶点编号char Name[20];//顶点名称}VertexType;// 顶点typedef int VRType; //顶点间关系，即权值，-1表示权值（距离）无穷大typedef void *InfoType;typedef enum {DG,DN,UDG,UDN} GrapKind;//图的种类{有向图，有向网，无向图，无向网}typedef struct{VRType Distance; //弧长，顶点间距离，-1表示该弧不存在（距离无穷大）InfoType Info; //与该弧相关信息的指针}ARcCell,*pAdjMatrx; //弧，邻接矩阵指针typedef struct{int Prior; //上一个节点VRType Distance; //从起始节点到该节点的路程}PathPoint,*Path; //路径节点，路径typedef struct{VertexType *vexs; //顶点向量pAdjMatrx Arcs; //邻接矩阵int Vexsnum,Arcnum; //图的当前顶点数和弧数GrapKind kind; //图的种类{有向图，有向网，无向图，无向网}}MGraph; //图（二）每个模块的分析（1）主程序模块int main(){MGraph Graph; //图FILE *fp; //图文件Path ShortestPath;//最短路径VertexType vexs1,vexs2;//起点，终点BOOL CONT='Y';//是否继续//加载交通图if ((fp=fopen("铁路交通图.txt","r"))==NULL){return FALSE;}InitGraph(Graph,fp);fclose(fp);while (CONT=='Y'){//计算起始点间的路径printf("请输入出发城市编号：");scanf("%d",&vexs1.Num);printf("请输入目的城市编号：");scanf("%d",&vexs2.Num);//获取最短路径并输出if(vexs1.Num<0||vexs1.Num>=Graph.Vexsnum||vexs2.Num<0||vexs2.Num>=Graph.Vexsnum) {printf("暂时没有您要的城市信息！\n");}GetPath(Graph,vexs2,vexs1,ShortestPath);//是否继续printf("是否继续？Y—继续N—退出\n");getchar();CONT=getchar();}return 0;}（2）初始化地图模块BOOL InitGraph(MGraph &Graph,FILE *fp){int i,j;//初始化地图节点fscanf(fp,"%d",&Graph.Vexsnum);//获取地图节点数Graph.vexs=(VertexType *)calloc(sizeof(VertexType),Graph.Vexsnum);//为节点分配内存if (Graph.vexs==NULL){printf("初始化失败");return FALSE;}for (i=0;i<Graph.Vexsnum;i++)//获取节点信息{fscanf(fp,"%d %s",&Graph.vexs[i].Num,Graph.vexs[i].Name);printf("%d %s\n",Graph.vexs[i].Num,Graph.vexs[i].Name);}//初始化地图路径Graph.Arcs=(pAdjMatrx)calloc(sizeof(ARcCell),Graph.Vexsnum*Graph.Vexsnum);//为路径分配内存if (Graph.Arcs==NULL){printf("初始化失败");return FALSE;}for (i=0;i<Graph.Vexsnum;i++)//获取路径信息{for (j=0;j<Graph.Vexsnum;j++){fscanf(fp,"%d",&Graph.Arcs[i*Graph.Vexsnum+j].Distance);}}return TRUE;}（3）获取最短路径模块BOOL GetPath(MGraph Graph,VertexType vexs1,VertexType vexs2,Path &ShortestPath){int i,j;int disNum;//当前节点最短弧的尾节点（当前行的位置）ShortestPath=(Path)calloc(sizeof(PathPoint),Graph.Vexsnum*Graph.Vexsnum);for (j=0;j<Graph.Vexsnum;j++)//加载第一行{ShortestPath[j].Distance=Graph.Arcs[vexs1.Num*Graph.Vexsnum+j].Distance;ShortestPath[j].Prior=vexs1.Num;}//加载其余行for (i=0;i<Graph.Vexsnum-1;i++){//获取路径（弧）最短节点GetShortestPathPoint(&ShortestPath[i*Graph.Vexsnum],Graph.Vexsnum,disNum);for (j=0;j<Graph.Vexsnum;j++){if (ShortestPath[i*Graph.Vexsnum+j].Distance>=0)//当前节点已有路径{ //判断是否有新路径，以及新路径是否比当前路径更短//有新路径，且新路径不比当前路径更短，则选择新路径if (Graph.Arcs[disNum*Graph.Vexsnum+j].Distance>=0&&(Graph.Arcs[disNum*Graph.Vexsnum+j].Distance+ShortestPath[i*Graph.Vexsnum+disNum]. Distance<ShortestPath[i*Graph.Vexsnum+j].Distance)){ShortestPath[(i+1)*Graph.Vexsnum+j].Distance=Graph.Arcs[disNum*Graph.Vexsnum+j].Dista nce+ShortestPath[i*Graph.Vexsnum+disNum].Distance;ShortestPath[(i+1)*Graph.Vexsnum+j].Prior=disNum;}else{//没有新路径，或新路径不比当前路径更短，保留当前路径ShortestPath[(i+1)*Graph.Vexsnum+j].Distance=ShortestPath[i*Graph.Vexsnum+j].Distance;ShortestPath[(i+1)*Graph.Vexsnum+j].Prior=j;}}else//当前节点没有路径{//判断是否有新路径，有新路径选择新路径if (Graph.Arcs[disNum*Graph.Vexsnum+j].Distance>=0){ShortestPath[(i+1)*Graph.Vexsnum+j].Distance=Graph.Arcs[disNum*Graph.Vexsnum+j].Dista nce+ShortestPath[i*Graph.Vexsnum+disNum].Distance;ShortestPath[(i+1)*Graph.Vexsnum+j].Prior=disNum;}else{//没有新路径，保留当前路径ShortestPath[(i+1)*Graph.Vexsnum+j].Distance=ShortestPath[i*Graph.Vexsnum+j].Distance;ShortestPath[(i+1)*Graph.Vexsnum+j].Prior=j;}}}}//打印最短路径PrintShortestPath(Graph,vexs1,vexs2,ShortestPath);//初始化标记节点GetShortestPathPoint(&ShortestPath[i*Graph.Vexsnum],0,disNum);return TRUE;}（4）获取最短路径节点模块BOOL GetShortestPathPoint(Path ShortestPath,int Count,int &DisNum){int i;int Dis=1<<30;//Dis为从路径ShortestPath开始的Count个节点中最小值static char IsSelected[50];//标记节点是否选择过//如果Count=0，执行初始化if (Count==0){for (i=1;i<50;i++){IsSelected[i]=0;//全部置为未选过}return FALSE;}//找到未选择过的最小路径节点for (i=0;i<Count;i++){ //未选择，路程更短，可通if ((!IsSelected[i])&&(ShortestPath[i].Distance<Dis)&&(ShortestPath[i].Distance>=0)){Dis=ShortestPath[i].Distance;DisNum=i;//选择该节点坐标}}IsSelected[DisNum]=1;//将选择的节点定义为以选择return TRUE;}（5）打印最短路径模块BOOL PrintShortestPath(MGraph Graph,VertexType vexs1,VertexType vexs2,Path ShortestPath) {int i,j;//j为当前节点的前驱j=vexs2.Num;//打印最短路程printf("最短距离是%d千米，路径为：\n",ShortestPath[(Graph.Vexsnum-1)*Graph.Vexsnum+j].Distance);for (i=Graph.Vexsnum-1;i>=0;i--){if (//(ShortestPath[i*Graph.Vexsnum+j].Distance!=-1)&&(ShortestPath[i*Graph.Vexsnum+j].Prior!=j)){printf("%s ",Graph.vexs[j].Name);//打印该节点j=ShortestPath[i*Graph.Vexsnum+j].Prior;//j置为当前节点的前驱}}printf("%s \n",Graph.vexs[vexs1.Num].Name);//打印终点return TRUE;}(四)程序使用说明1．程序使用说明（1）本程序的运行环境为VS2010。
