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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 交通咨詢系統(tǒng)中的 最短路徑 一、問題描述 二、基本要求 三、算法思想 四、數(shù)據(jù)結(jié)構(gòu) 問題描述建立交通圖的存儲結(jié)構(gòu)、解決單源最短路徑問題、再實(shí)現(xiàn)兩個地點(diǎn)最短路徑問題，也就是實(shí)現(xiàn)迪杰斯特拉和弗洛伊德方法。基本要求（1）建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；（2）解決單元最短路徑問題；（3）求兩座城市頂點(diǎn)之間的最短路徑問題 。算法思想迪杰斯特拉算法的思想是：頂點(diǎn)v1為源點(diǎn)，集合S的初態(tài)只包含頂點(diǎn)v1,數(shù)組dist記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短距離，其初值為disti=costv1i,i=1,2,n.從S之外的頂點(diǎn)集合V-S中選出一個W,使distW最小，如此重復(fù)直到S中包含V的所有頂點(diǎn)。

2、費(fèi)洛伊德算法的思想:首先考慮路徑和是否存在。如果存在，則比較路徑和的路徑長度，取長度較短者為當(dāng)前所求的最短路徑。然后考慮從Vi到Vj是否含有頂點(diǎn)V2為中間頂點(diǎn)的路徑,若沒有，則其最短路徑為之前所求，若有，則可以分解為和,而其為前一次找到的中間頂點(diǎn)序號不大于一的最短路徑，將兩者相加記為路徑長度，比較該長度與前一次的中間頂點(diǎn)序號不大于一的，取其最短的作為當(dāng)前求的從Vi到Vj的中間頂點(diǎn)長度不大于二的最短路徑，直到選出不大于N的最短路徑為止。數(shù)據(jù)結(jié)構(gòu)部分算法（1）建立有向圖的存儲結(jié)構(gòu)：void CreateMGraph(MGraph *G,int n,int e)int i,j,k,w;for(i=1

3、;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;printf(輸入%d條邊的i、j及w:n,e);for(k=1;karcsij=w;printf(有向圖的存儲結(jié)構(gòu)建立完畢!n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5d,i);v=p2i;while(v!=0)printf(-%d,v);v=p2v;printf(n);迪杰斯特拉算法（2）迪杰斯特拉算法：void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,min

4、;enum boolean SMVNum;for(v=1;varcsv1v;if(D2vMaxint）p2v=v1;elsep2v=0;D2v1=0;sv1=TRUE;for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw&D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;p2w=v;printf(路徑長度 路徑n);費(fèi)洛伊德算法（3）費(fèi)洛伊德算法：void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=n;i+)for(j=1;jarcsij!=Maxint)pij=j;elsepij;Dij=G-arcsij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+