單源最短路徑

《單源最短路徑》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、單源最短路徑xie_dream給定帶權(quán)有向圖G=(V,E)和源點(diǎn)u,求從點(diǎn)u到其他各頂點(diǎn)的最短距離Dijkstra算法基本思想是：設(shè)置一個(gè)集合Ｓ存放已經(jīng)找到最短路徑的頂點(diǎn)，Ｓ的初始狀態(tài)只包含源點(diǎn)u,設(shè)置另一個(gè)集合Ｔ，Ｔ＝Ｖ-Ｓ，存儲(chǔ)原圖中不在Ｓ集中的點(diǎn)，即Ｓ的補(bǔ)集。假設(shè)從源點(diǎn)u到vi的有向邊為最短路徑，以后每求得一條最短路徑v,…,vk就將vk加入集合Ｓ中，并將路徑v,…vk,vi與原來的假設(shè)相比較，取路徑長(zhǎng)度較小者為最短路徑。重復(fù)上述過程，直到集合Ｖ中全部頂點(diǎn)加入到集合Ｓ中STuviSTuvivkST

2、uvivkuv2v3v4v133512992S集合紅線右側(cè)全為Ｔ集合1)先假設(shè)v1,v2,v3,v4與u相連的邊就是最短路徑dist[v1]=3,dist[v2]=2;dist[3]=9;dist[4]=10v2v3v4v1331012992S集合uu2)找一個(gè)離u最近的點(diǎn)加入S集合(這里是不是有點(diǎn)象前一講中的MST的Prim算法),即為v2v2v3v4v1331012992S集合u2)找一個(gè)離u最近的點(diǎn)加入S集合(這里是不是有點(diǎn)象前一講中的MST的Prim算法),即為v2v2v3v4v13310129

3、92S集合u再用v2去檢查從v2可到達(dá)的點(diǎn)的原先的所有假設(shè)發(fā)現(xiàn)dist[v4]>dist[v2]+g[v2][v4],更新dist[v4]v2v3v4v1331012992S集合u3)按上一步同樣的方法找到v1加入到S集合中v2v3v4v1331012992S集合u3)按上一步同樣的方法找到v1加入到S集合中v2v3v4v1331012992S集合u４)按上一步同樣的方法找到v4加入到S集合中,這時(shí)dist[v3]=9

4、t[v4]=4了！v2v3v4v1331012992S集合u５)４加入Ｓ集合中，同樣發(fā)現(xiàn)dist[v3]>dist[v4]+g[v4][v3],更新！v2v3v4v1331012992S集合u算法實(shí)現(xiàn)過程1,初始化dist[]和color[]2,while(s集合中的元素個(gè)數(shù)小于n)在dist[]中求最小值，并同樣記錄下標(biāo)k用dist[k]去修改k一步直接可達(dá)的點(diǎn)的dist[]將頂點(diǎn)k放入Ｓ集合中，染為紫色詳細(xì)代碼/*Author:PrimeMusic_FanCreatedon2010年4月29日,下午

5、1:46*/#include#include#definearr110#defineblue0#definepurple1#definemax_int214748364intn;//thenumberofvertexsintm;//thenumberofedgesintg[arr][arr];//g[i][j]indicatesthedistancebetweeniandjintpath[arr];//path[i]recordtheshorestpathfroms

6、ourceutoiintdist[arr];//dist[i]indicatestheshortestdistancefromutoiintst;//thesourcevertexintcolor[arr];//colorthevertexvoidDijkstra(intst){for(inti=1;i<=n;++i){color[i]=blue;dist[i]=g[st][i];//先假設(shè)源點(diǎn)u到其他點(diǎn)的直接相連邊的長(zhǎng)度就為最短距離path[i]=st;//假設(shè)都是從u直接通過一條有向邊到達(dá)}dist

7、[st]=0;color[st]=purple;intnumS=1;//S集合中元素的個(gè)數(shù),已經(jīng)加入了源點(diǎn)，所以為１while(numS++dist[i]){minDis=dist[i];k=i;}}//print

8、f("k=%d",k);if(k==-1)//說明找不到與源點(diǎn)相連的點(diǎn)，算法結(jié)束break;color[k]=purple;//找到點(diǎn)k，加入Ｓ集合中，并染為紫色//下一步，用dist[k]去檢查原先的所有不在Ｓ集合，即Ｔ集合中所有點(diǎn)的假設(shè)for(inti=1;i<=n;++i){if(color[i]==purple)continue;if(dist[i]>dist[k]+g[k][i]){//通過點(diǎn)k可以使源點(diǎn)到i點(diǎn)的距離變小，更新