建立交通网并求两点间最短路径.docx

#includestdio.h#includestring.h#define INFINITY 1000000//表示不可达#define MAX_VERTEX_NUM 50#define FALSE 0#define TRUE 1//enum boolean {typedef// char city[10]; struct Vexs{char ch[20];//用来存放城市名}Vexs;typedef struct{Vexs vexs[MAX_VERTEX_NUM];//顶点向量int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵int vexnum,arcnum;//图当顶点数和弧数}Mgraph;//无向图int Locatevex(Mgraph G,Vexs v){int j=-1,k;for(k=0;kG.vexnum;k++){if(strcmp(G.vexs[k].ch ,v.ch )==0 )/*for(i=0;G.vexs[k].ch[i]!=\0;i++){if(G.vexs[k].ch[i]!=v.ch[i])break;}if(G.vexs[k].ch[i]==\0)*/{j=k;return j;}}return j;}void Create(Mgraph G)//用邻接矩阵存储方式，构造有向图G{ Vexs v1,v2;int w,i,j,k;printf(请输入图的顶点数和弧数\n);scanf(%d,%d,G.vexnum,G.arcnum);printf(请输入各顶点的值\n);for(i=0;iG.vexnum;i++)scanf(%s,G.vexs[i]);//构造顶点向量for(i=0;iG.vexnum;i++)//初始化邻接矩阵for(j=0;jG.vexnum;j++)G.arcs[i][j]=INFINITY;for(k=0;kG.arcnum;k++)//构造邻接矩阵，有多少条弧，循环多少次{printf(请输入一条边的起点\n);scanf(%s,v1);//输入一条边依附的顶点及权值printf(请输入一条边的终点\n);scanf(%s,v2);printf(请输入该边权值\n);scanf(%d,w);i=Locatevex(G,v1);j=Locatevex(G,v2);//确定v1和v2在G中的位置G.arcs[i][j]=w;G.arcs[j][i]=w;//无向网v1,v2的权值}}void print(Mgraph G)//输出建好的图{int i,j,k=0;for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++){printf(%d\t,G.arcs[i][j]);k++;//控制换行if(k==G.vexnum){printf(\n);k=0;}}}void ShortestPath(Mgraph G ,int v0){int path[MAX_VERTEX_NUM],D[MAX_VERTEX_NUM];//存放最短路径，存最短路径长度 int v,w,i; int final[MAX_VERTEX_NUM];for (v=0; vG.vexnum; ++v) {final[v]=FALSE; D[v]=G.arcs[v0][v];if (D[v]INFINITY) path[v]=v0;else path[v]=-1; }//forpath[v0] = 0; final[v0]=TRUE; //初始化V0属于S集合for (i=1;iG.vexnum; i++)//其余顶点{int min=INFINITY; v=-1; //当前所知离v0最近的距离for( w=0;wG.vexnum; ++w)if (!final[w]D[w]min) //w顶点在V-S中 {v=w;min=D[w]; } //w离v0最近if (v!=-1) { final[v]=TRUE; //离v0最近的v加入S for ( w=0;wG.vexnum; ++w) //更新当前最短路径及距离if (!final[w] (min+G.arcs[v][w]D[w]))//修改D、P{ D[w]=min+G.arcs[v][w]; path[w]=v; }}//if }//for printf(最短路径长度 路径\n);//输出到所有顶点的最短路径for(i=0;iG.vexnum ;i++){printf(%5d,D[i]);printf(%5d,i);v=