迪杰斯特拉算法

迪杰斯特拉算法實現(xiàn)第九組11123529-羅凱耀11123575-王鳴迪杰斯特拉--算法思想按從某頂點到其它頂點的路徑長度遞增的方式,逐漸求到各頂點的最短路徑。設(shè)給定源點為Vs，S為已求得最短路徑的終點集，開始時令S={Vs}。當(dāng)求得第一條最短路徑(Vs，Vi)后，S為{Vs，Vi}。根據(jù)以下結(jié)論可求下一條最短路徑。設(shè)下一條最短路徑終點為Vj，那么Vj只有：◆源點到終點有直接的弧<Vs，Vj>；◆從Vs出發(fā)到Vj的這條最短路徑所經(jīng)過的所有中間頂點必定在S中。即只有這條最短路徑的最后一條弧才是從S內(nèi)某個頂點連接到S外的頂點Vj。假設(shè)定義一個數(shù)組dist[n]，其每個dist[i]分量保存從Vs出發(fā)中間只經(jīng)過集合S中的頂點而到達(dá)Vi的所有路徑中長度最小的路徑長度值，那么下一條最短路徑的終點Vj必定是不在S中且值最小的頂點，即：dist[i]=Min{dist[k]|Vk∈V-S}利用上述公式就可以依次找出下一條最短路徑。迪杰斯特拉-算法思想源迪杰斯特拉算法

--數(shù)據(jù)組織源有n個結(jié)點的網(wǎng)絡(luò)數(shù)據(jù)源已確定結(jié)點集S待選結(jié)點集V-S結(jié)點臨時最短路徑長度結(jié)點臨時最短路徑迪杰斯特拉算法—步驟①令S={Vs}，用帶權(quán)的鄰接矩陣表示有向圖，對圖中每個頂點Vi按以下原那么置初值：②選擇一個頂點Vj，使得：Distance[j]=Min{Distance[k]|Vk∈V-S}Vj就是求得的下一條最短路徑終點，將Vj并入到S中，即S=S∪{Vj}。③對V-S中的每個頂點Vk，修改dist[k]，方法是：假設(shè)Distance[j]+Wjk<Distance[k]，那么修改為：Distance[k]=Distance[j]+Wjk(Vk∈V-S)④重復(fù)②，③，直到S=V為止。Wsii≠s且<vs,vi>∈E，wsi為弧上的權(quán)值∞i≠s且<vs,vi>不屬于Edist[i]=0i=s迪杰斯特拉算法—實現(xiàn)voidDijkstra(MGraphg,intstart,intend){intdist[MAXV],path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;i<g.n;i++){dist[i]=g.edges[start][i];//dist數(shù)組初始化s[i]=0;if(g.edges[start][i]<INF) path[i]=start;else path[i]=-1;//path數(shù)組初始化}s[start]=1;//頂點start參加頂點集合s path[start]=0;for(i=0;i<g.n;i++)//選擇不在集合s中且具有最短路徑的頂點{mindis=INF;for(j=0;j<g.n;j++){if(s[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}}s[u]=1;//將頂點u參加集合for(j=0;j<g.n;j++)//修改dist和path{if(s[j]==0){ if((g.edges[u][j]<INF)&&(dist[u]+g.edges[u][j]<dist[j])){dist[j]=dist[u]+g.edges[u][j];path[j]=u;}}}}Dispath(g,dist,path,s,g.n,start,end);}EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF運(yùn)算過程表鄰接矩陣圖數(shù)據(jù)源——鄰接矩陣已確定結(jié)點集S待選結(jié)點集V-S結(jié)點臨時最短路徑長度——Distance數(shù)組結(jié)點臨時最短路徑——Path數(shù)組Dijkstra算法--數(shù)據(jù)組織運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF鄰接矩陣圖例：計算從A點出發(fā)的單源最短路徑運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF鄰接矩陣圖例：計算從A點出發(fā)的單源最短路徑運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF鄰接矩陣圖例：計算從A點出發(fā)的單源最短路徑運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF鄰接矩陣圖例：計算從A點出發(fā)的單源最短路徑運(yùn)算過程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF鄰接矩陣圖例：計算從A點出發(fā)的單源最短路徑運(yùn)算結(jié)果Dijkstra算法—例子úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050BACDEFBACDEF鄰接矩陣圖EFDBCA8510715通過Distance數(shù)組得到最短路徑長度：D: