數(shù)據(jù)結(jié)構(gòu)最短路徑

1、圖的最短路徑一、實驗?zāi)康氖箤W(xué)生熟悉最短路徑的算法實現(xiàn)二、掌握帶權(quán)圖的存儲結(jié)構(gòu)和處理方法硬件：每個學(xué)生需配備計算機一臺。操作系統(tǒng)：DOS或Windows軟件：DOS或 Windows操作系統(tǒng)+Turbo C;三、實驗要求1.能夠獨立完成帶權(quán)圖的存儲和最短路徑的生成四、實驗內(nèi)容現(xiàn)在假設(shè)我國鐵路交通圖如下(權(quán)值表示距離)，請用合適的存儲結(jié)構(gòu)將下圖存儲到計算機中方便進行處 理?，F(xiàn)在我想以最小的代價從徐州出發(fā)到達其他目的地，請用Dijkstra算法實現(xiàn)我的要求的路徑。#include stdio.h#include malloc.h”typedef struct(int *vexs;int *arcs;

2、int vexnum;graph_hc;typedef struct(int adjvex;int lowcost;markedg_hc;graph_hc *initgraph_hc()(int i,j;graph_hc*g;g=(graph_hc*)malloc(sizeof(graph_hc);g-vexnum=25;g-vexs=(int*)malloc(g-vexnum*sizeof(int);g-arcs=(int*)malloc(g-vexnum*sizeof(int*);for(i=0;ivexnum;i+)g-arcsi=(int*)malloc(g-vexnum*sizeof

3、(int);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)(g-arcsij=0;return g;void creategraph_hc(graph_hc *g)(int i,j;for(i=0;ivexnum;i+)g-vexsi =i;g-arcs09=1892; g-arcs13=242;g-arcs24=668; g-arcs29=1145;g-arcs35=305; g-arcs46=137;g-arcs411=695; g-arcs56 =704;g-arcs57=397; g-arcs612=674;g-arcs89=216; g-arcs910=

4、676;g-arcs1011=511;g-arcs1013=842;g-arcs1112=349;g-arcs1114=534;g-arcs1215=651;g-arcs1316=110;g-arcs1317 =967;g-arcs1418 =409;g-arcs1519=825;g-arcs1617=639;g-arcs1718=902;g-arcs1721=607;g-arcs1819 =367;g-arcs1821=672;g-arcs1823=675;g-arcs1920 =622;g-arcs2122 =255;g-arcs2324=140;for(i=0;ivexnum;i+)fo

5、r(j=i;jvexnum;j+)if(g-arcsij)g-arcsji =g-arcsij;void printgraph_hc(graph_hc*g)int x,y;printf(n城市間連通圖為:n);for(x=0;xvexnum;x+)for(y=x;yvexnum;y+)if(g-arcsxy)printf(%d,%d)距離:dt”,x,y,g-arcsxy);int selectnearvex_hc(markedg_hc*mark,int *flag,int num)int j;int nearestv;int lowcost=32767;for(j=0;j num;j +)i

6、f(flagj !=1&markj .lowcostlowcost)nearestv=j;lowcost=markj.lowcost;flagnearestv=1;return nearestv;void markothervex_hc(graph_hc*g,markedg_hc*mark,int nearestvjnt num,int*flag)int j;for(j=0;j arcsnearestvj0)if(flagj!=1)if(markj.lowcost(marknearestv.lowcost+g-arcsnearestvj)markj.lowcost= marknearestv.

7、lowcost+g-arcsnearestvj;markj.adjvex=nearestv; void shortestpath_hc(graph_hc*g,markedg_hc*mark,int start)(int i,num;int *flag;int nearestv;num=g-vexnum;flag=(int *)malloc(num)*sizeof(int);flagstart=1;for(i=0;ivexnum;i+)(marki.adjvex=start;if( g-arcsstarti 0)(marki .lowcost=g-arcsstarti;else(marki.lo

8、wcost=32767;for(i= 1;ivexnum;i+)(nearestv=selectnearvex_hc(mark,flag,num);markothervex_hc(g,mark,nearestv,num,flag);void printshortpath_hc(graph_hc*g,markedg_hc*mark,int start)(int i,j,k,path25;for(i=0;ivexnum;i+)(if(i!=start)(printf(從 d到d最短路徑為:d; ,start,i,marki.lowcost);printf(途經(jīng):)；k=0;pathk=i;j=ma

9、rki.adjvex;while(j !=start)(path+k=j;j=markj.adjvex;printf(%d”,start);for(j=k;j=0;j-)printf(,%d”,pathj);printf(.n);main()(int city;graph_hc * g;markedg_hc *mark;g=initgraph_hc();creategraph_hc(g);printf(城市名稱/代號:)；printf(-烏魯木齊/0,哈爾濱/1,呼和浩特/2,長春/3,北京/4,);printf(沈陽/5,天津/6,大連/7,西寧/8,蘭州/9,西安/10,鄭州/11,);p

10、rintf(徐州/12,成都/13,武漢/14,上海/15,昆明/16,貴陽/17,株州/18,”);printf(南昌/19,福州/20,柳州/21,南寧/22,廣州/23,深圳/24.n);printgraph_hc(g);mark=(markedg_hc*)malloc(g-vexnum*sizeof(markedg_hc);printf(n 輸入起始城市:);scanf(%d”,&city);shortestpath_hc(g,mark,city);printshortpath_hc(g,mark,city);D:Program Fi lesCYuYanbi nwv/temp.exep

11、rintf(-n 作者:黃晨，阻市名稱,代號:烏魯木齊向，哈爾濱/1,呼和浩特也，長春北京/沈陽市，天津用, 大連凡西寧用，蘭州西，西安/10,鄭州/11,徐州，蔑，成都713,武況/14,上海，比, 昆明依,貴陽街 株州/迅南昌福州/X柳州仞，南寧仞，廣州/路 深圳山.城市間連通圖為: (0,9)距離：1892 (4, 6)距離：13吊 缶,9)距離6 (11,14)已&離：534 (15,19)距離:實5 (18, W1)距離:”W (1, 3)距離:幽2 (4,11)距離:即5 但，10)距離:源 (12, 15)距離:洗1 (16, 17)距離:明9 (18, W3)距離:”5(制)距

12、離：668(5盤)距離：T04康離：511(13, 16)距離：11。 (17, 18)距離：舞 (19, 20)距離:如 (% 9)距離：1145 (5,曰距離：3卯 (10,偵施離：&4 (13, 1日距離:明吊 (17, 1)距離:河 (21,露)距離：W55 (3, 5)距離：305 (6,12)距離:衍4 (11,距離：349 (14,距離:409 (18, 19)距離：3衍 (23, 24)距離：14口途經(jīng)：1七 11,10, 9,0.途經(jīng)：12, 6, 5, 3,1.途經(jīng)：12, 6, 4,2.途經(jīng)：12, 6, 5,3.途經(jīng):12, 6,4.途經(jīng)：12, 6, 5.途經(jīng)：12,

13、 6.途經(jīng)：12, 6, 5,7.途經(jīng)：12,11, 10, 9,8.途經(jīng)：12,11, 10,9.途經(jīng)：12,11,10.途經(jīng)途經(jīng)：12, 11,10, 13.途經(jīng):12,11,14.途經(jīng)：12,15.途經(jīng)：12, 11,10, 13,16.途經(jīng)：12, 11,14, 18,17.途經(jīng)：12, 11,14, 18.途經(jīng)：12, 15,19.途經(jīng)：12, 15,19, 20.途經(jīng)：12, 11,14, 18, 21.途經(jīng):12, 11,14, 18, 21, 22.途經(jīng)：12, 11,14, 18, 23.途經(jīng)：12,11,14,18, 23, 24.愉人起始城市:1W 1W到口最起路徑為：3428; 以12薊1最短路徑為：1925; 以12薊2最短路徑為：1479; 以12薊3最短路徑為：1683; 以12薊4最短路徑為：811;從12到5最短路徑為：137S; 以12至麗最短路徑為：674; 從12到7最短路徑為：1775; 從12到8最短路徑為：1752; 從膏到9最短路徑為：1536; 虹薊10最癥路徑為:860; 虹薊M最短路徑為：349; 虹薊