迪杰斯特拉算法講課教案.ppt

《迪杰斯特拉算法講課教案.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、迪杰斯特拉算法實(shí)現(xiàn)第九組11123529-羅凱耀11123575-王鳴迪杰斯特拉--算法思想按從某頂點(diǎn)到其它頂點(diǎn)的路徑長度遞增的方式,逐漸求到各頂點(diǎn)的最短路徑。設(shè)給定源點(diǎn)為Vs，S為已求得最短路徑的終點(diǎn)集，開始時(shí)令S={Vs}。當(dāng)求得第一條最短路徑(Vs，Vi)后，S為{Vs，Vi}。根據(jù)以下結(jié)論可求下一條最短路徑。設(shè)下一條最短路徑終點(diǎn)為Vj，則Vj只有：◆源點(diǎn)到終點(diǎn)有直接的弧；◆從Vs出發(fā)到Vj的這條最短路徑所經(jīng)過的所有中間頂點(diǎn)必定在S中。即只有這條最短路徑的最后一條弧才是從S內(nèi)某個(gè)頂點(diǎn)連接到S外的頂點(diǎn)Vj。若定義一個(gè)數(shù)組dist[n]，其每個(gè)di

2、st[i]分量保存從Vs出發(fā)中間只經(jīng)過集合S中的頂點(diǎn)而到達(dá)Vi的所有路徑中長度最小的路徑長度值，則下一條最短路徑的終點(diǎn)Vj必定是不在S中且值最小的頂點(diǎn)，即：dist[i]=Min{dist[k]

3、Vk∈V-S}利用上述公式就可以依次找出下一條最短路徑。迪杰斯特拉-算法思想源迪杰斯特拉算法--數(shù)據(jù)組織源有n個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)數(shù)據(jù)源已確定結(jié)點(diǎn)集S待選結(jié)點(diǎn)集V-S結(jié)點(diǎn)臨時(shí)最短路徑長度結(jié)點(diǎn)臨時(shí)最短路徑迪杰斯特拉算法—步驟①令S={Vs}，用帶權(quán)的鄰接矩陣表示有向圖，對(duì)圖中每個(gè)頂點(diǎn)Vi按以下原則置初值：②選擇一個(gè)頂點(diǎn)Vj，使得：Distance[j]=Min{Distance[

4、k]

5、Vk∈V-S}Vj就是求得的下一條最短路徑終點(diǎn)，將Vj并入到S中，即S=S∪{Vj}。③對(duì)V-S中的每個(gè)頂點(diǎn)Vk，修改dist[k]，方法是：若Distance[j]+Wjk∈E，wsi為弧上的權(quán)值∞i≠s且不屬于Edist[i]=0i=s迪杰斯特拉算法—實(shí)現(xiàn)voidDijkstra(MGraphg,intstart,intend){intdist[MAXV],path[MAXV]

6、;ints[MAXV];intmindis,i,j,u;for(i=0;i

7、]

8、cePath4DistancePath5(n-1)DistancePathEFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF運(yùn)算過程表鄰接矩陣圖數(shù)據(jù)源——鄰接矩陣已確定結(jié)點(diǎn)集S待選結(jié)點(diǎn)集V-S結(jié)點(diǎn)臨時(shí)最短路徑長度——Distance數(shù)組結(jié)點(diǎn)臨時(shí)最短路徑——Path數(shù)組Dijkstra算法--數(shù)據(jù)組織已完成結(jié)點(diǎn)集，本次最近點(diǎn)ABCDEF1{A,},CDistance0￥530￥￥PathA-1AA-1-12DistancePath3Di

9、stancePath4DistancePath5(n-1)DistancePath運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF鄰接矩陣圖例：計(jì)算從A點(diǎn)出發(fā)的單源最短路徑已完成結(jié)點(diǎn)集，本次最近點(diǎn)ABCDEF1{A,},CDistance0￥530￥￥PathA-1AA-1-12{A,C},FDistance020530￥12PathACAA-1C3DistancePath4DistancePat

10、h5(n-