城市最短路径查询(C语言)

《城市最短路径查询(C语言)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#defineINFINITY32767//INF表示无穷大#defineMAX_VERTEX_NUM10typedefstruct{intedge;//边的权值}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//两点之间路径长度typedefstruct//景点信息{charname[30];intnum;}infotype;typedefstruct{infotypevexs[MAX_VERTEX

2、_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph;MGraphb;//函数声明MGraphInitGraph();voidFloyd(MGraph*G);voidMenu();voidcmd();MGraphInitGraph()//初始化顶点和权值{MGraphG;inti,j;G.vexnum=6;G.arcnum=6;for(i=0;i

3、strcpy(G.vexs[1].name,"襄樊");strcpy(G.vexs[2].name,"随州");strcpy(G.vexs[3].name,"武汉");strcpy(G.vexs[4].name,"黄石");strcpy(G.vexs[5].name,"荆州");strcpy(G.vexs[6].name,"宜昌");for(i=0;i

4、rcs[0][1].edge=G.arcs[1][0].edge=145;G.arcs[1][2].edge=G.arcs[2][1].edge=124;G.arcs[1][5].edge=G.arcs[5][1].edge=188;G.arcs[1][6].edge=G.arcs[6][1].edge=169;G.arcs[2][3].edge=G.arcs[3][2].edge=149;G.arcs[2][5].edge=G.arcs[5][2].edge=187;G.arcs[3][4].edge=G.arcs[4][3].edge=8

5、3;G.arcs[4][5].edge=G.arcs[5][4].edge=269;G.arcs[5][6].edge=G.arcs[6][5].edge=178;returnG;}/*Floyd算法求最短路径*/voidFloyd(MGraph*G){intv,u,i,w,k,j,flag=1,p[11][11][11],D[11][11];for(v=0;vvexnum;++v)for(w=0;wvexnum;++w){D[v][w]=G->arcs[v][w].edge;//从v到w之间的路径长度赋值给D[v][w]fo

6、r(u=0;uvexnum;++u)p[v][w][u]=0;//u不是v到w之间最短路径上的顶点if(D[v][w]vexnum;++u)for(v=0;vvexnum;++v)for(w=0;wvexnum;++w)if(D[v][u]+D[u][w]

7、vexnum;++i)p[v][w][i]=p[v][u][i]

8、

9、p[u][w][i];//分半开始找途径i，v和u之间或w和u之间的路径长度}while(flag){printf("请输入出发点和目的地的编号（注意：输入编号时用空格号分割）:");scanf("%d%d",&k,&j);if(k<0

10、

11、k>G->vexnum

12、

13、j<0

14、

15、j>G->vexnum){printf("景点编号不存在!请重新输入起点和终点的编号:");scanf("%d%d",&k,&j);}if(k>=0&&kvexnum&&j>=0&&j

16、->vexnum)flag=0;}printf("");printf("%s",G->vexs[k].name);for(u=0;uvexnum;++u