lxk实验九-最短路径问题

《lxk实验九-最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验九最短路径问题一、实验目的1、掌握图的相关概念。2、掌握图的逻辑和存储结构。3、掌握图的各种应用的实现。二、实验内容给定一个无向网，可以求得任意一对顶点之间的最短路径。以邻接矩阵为存储结构，实现弗洛伊德算法求解每一对顶点之间的最短路径及最短路径长度。下面是全国铁路交通部分数据，顶点表示城市，共有26个顶点，边表示城市之间的距离，共有30条边，求解全国铁路交通图屮每两个城市Z间的最短距离。三、测试数据全国铁路交通数据：（26个城市代码）0乌鲁木齐1呼和浩特2哈尔滨3西宁4兰州5成都6昆明7贵阳8南宁9柳州10株洲1

2、1广州12深圳13南昌14福州15上海16式汉17西安18郑州19徐州20北京21天津22沈阳23大连24长春25台北两个城市之间距离（公里）：乌鲁木齐兰州1892呼和浩特兰州1145呼和浩特北京668哈尔滨长春242西宁兰州216兰州西安676西安成都842西安郑州511成都昆明1100成都贵阳967昆明贵阳639贵阳柳州607柳州株洲672柳州南宁255贵阳株洲902株洲式汉409株洲广州675株洲南昌367广州深圳140南昌福州622南昌上海825武汉郑州534郑州北京695郑州徐州349徐州天津674徐州上海

3、651北京天津137天津沈阳704沈阳大连397沈阳长春305四、编码#include#include#includeusingnamespacestd;classMGraph{public:stringvertex[26];intvertexNum;inteNum;intarc[26][26];}；classFloyd{public:voidfdist(MGraphG){inti,j,k;stringt;for(i=0;i

4、(j=0;j

5、j]!=9999)path[i][j]=G.vertex[i]+n->,,+G.vertex

6、j];elsepath[i][j]=nn;}for(k=0;k

7、j]){dist[i][j]=dist[i]

8、[k]+dist[k]

9、j]；t=path[i][k];for(intc=t.size()-l;Uc]!=‘>';c一)t=t.substr(O,c);path[i][j]=t+path[k][j];}}voidSeek(inta,intb)cout«H路线：n«path[a]fb]«endl«H路程:H«dist[a]rbl«H公里u«endl;}private:stringpath[26][26];intdist[26][26];}；voidmain(){MGraphG;FloydT;stringt;G.vert

10、exNum=26;G.eNum=30;inti,j；for(i=0;i<26;i++)for(j=0;j<26;j++)G.arc[i][j]=9999;fstreamfilel,file2;filel.openCtxtl.txt");file2.open("txt2.txt");inttl,t2,t3;for(i=0;i<26;i++){filel»tl»t;G.vertex[tl]=t;}for(i=0;i<30;i++){file2»tl»t2»t3;G.arcftl][⑵=(3;G.arc[t2][t1]=t

11、3;Ifilel.close();file2.close();T.fdist(G);intc;cout«n查询请按1,退出请按0:n;cin»tl;{cout«"各城市对应编号:"«endl;for(inti=0;i<26;i++)cout«G.vertex[i]«M:H«i«M号”;}cout«endl;while(c){cout«H请输入查询的城市编号:n«endl;cin»i»j;T.Seek(ij);cout«H继续査询请按1,退出请按0。：”;cin»c;}systemCpause");)■_!・C:US

12、[：RS百B国尧VXSKTOPX程序縛习sy9999Debugsy9999.exe"-□I査询请按1,退出请按0:1各城市对应编号：马鲁木齐:0号呼和浩特:1号哈尔滨:2号西宁:3号兰州:4号成都:5号昆明:6号贵阳:7号南宁:8号柳州:9号株洲:10号广州：11号深#11:12号南昌：13号福州：14号上海:15号武汉:16号西安:17