最短路徑算法分類與應(yīng)用研究-文庫吧
2025-06-11 06:04 本頁面
【正文】 到該結(jié)點(diǎn)的深度+ 距離目標(biāo)最近的程度。算法原理：如圖有如下的狀態(tài)空間：（起始位置是A，目標(biāo)位置是P，字母后的數(shù)字表示節(jié)點(diǎn)的估價(jià)值）狀態(tài)空間圖搜索過程中設(shè)置兩個(gè)表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。算法中有一步是根據(jù)估價(jià)函數(shù)重排OPEN表。這樣循環(huán)中的每一步只考慮OPEN表中狀態(tài)最好的節(jié)點(diǎn)。算法描述：（1）初始狀態(tài)： OPEN=[A5]。CLOSED=[]。（2）估算A5，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[B4, C4, D6]。 CLOSED=[A5]（3）估算B4，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[C4, E5, F5, D6]。 CLOSED=[B4, A5]（4）估算C4；取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[H3, G4, E5, F5, D6]。CLOSED=[C4, B4, A5]（5）估算H3，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[O2, P3, G4, E5, F5, D6]。 CLOSED=H3C4, B4, A5]（6）估算O2，取得搜有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[P3, G4, E5, F5, D6]。 CLOSED=[O2, H3, C4, B4, A5]（7）估算P3，已得到解。三、BellmanFord算法適用條件和范圍：（1）單源最短路徑(從源點(diǎn)s到其它所有頂點(diǎn)v)；（2）有向圖和無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖)；（3）邊權(quán)可正可負(fù)(如有負(fù)權(quán)回路輸出錯(cuò)誤提示)；（4）差分約束系統(tǒng)。算法描述：（1）對(duì)每條邊進(jìn)行|V|次Relax操作；（2）如果存在（u,v）∈E使得dis[u]+wdis[v]，則存在負(fù)權(quán)回路；否則dis[v]即為s到v的最短距離，pre[v]為前驅(qū)。算法實(shí)現(xiàn)：（1）PASCA語言 For i:=1 to |V|1 do For 每條邊(u,v)∈E do Relax(u,v,w)。 For每條邊(u,v)∈E do If dis[u]+wdis[v] Then Exit(False)?。?）C/C++語言 void bellman_ford(int v) { for 1 to n initialize dist[v]。 for 2 to n1 (i) for 1 to n (j) for 1 to n (k) if edge[k][j] 0 amp。amp。 dist[k] edge[k][j]+dist[j] 更新當(dāng)前值 }四、TopologicalSort(拓?fù)渑判?算法適用條件和范圍：（1）AOV網(wǎng)(ActivityOnVertexNetwork)；（2）有向圖；（3）作為某些算法的預(yù)處理過程(如DP)。算法描述：（1）每次挑選入度為0的頂點(diǎn)輸出(不計(jì)次序)；（2）如果最后發(fā)現(xiàn)輸出的頂點(diǎn)數(shù)小于|V|，則表明有回路存在。算法實(shí)現(xiàn)：（1）數(shù)據(jù)結(jié)構(gòu)：adj:鄰接表。有4個(gè)域{u,v,w,next}；indgr[i]:頂點(diǎn)i的入度；stack[]:棧；（2）初始化:top=0(棧頂指針)；（3）將初始狀態(tài)所有入度為0的頂點(diǎn)壓棧；（4）I=0(計(jì)數(shù)器)；（5）While棧非空(top0)do①頂點(diǎn)v出棧；輸出v；計(jì)數(shù)器增1；②For與v鄰接的頂點(diǎn)udoa.dec(indgr[u])；b.Ifindgr[u]=0then頂點(diǎn)u入棧；（6）EXIT(I=|V|)。五、SSSPOnDAG算法適用條件和范圍：（1）DAG(DirectedAcyclicGraph,有向無環(huán)圖)；（2）邊權(quán)可正可負(fù)。算法描述：（1）Toposort；（2）IfToposort=FalseThenHALT(NotaDAG)；（3）For拓?fù)湫虻拿總€(gè)頂點(diǎn)udoForu的每個(gè)鄰接點(diǎn)vdoRelax(u,v,w)；（4）算法結(jié)束后：如有環(huán)則輸出錯(cuò)誤信息；否則dis[i]為s到i的最短距離，pre[i]為前驅(qū)頂點(diǎn)。算法實(shí)現(xiàn)：此算法時(shí)間復(fù)雜度O(V+E)，時(shí)間和編程復(fù)雜度低，如遇到符合條件的題目(DAG)，推薦使用。還有，此算法的步驟（3）可以在toposort中實(shí)現(xiàn)，這樣即減小了此算法復(fù)雜度的一個(gè)系數(shù)。六、Floyd算法適用范圍： （1）APSP(AllPairsShortestPaths)；（2）稠密圖效果最佳；（3）邊權(quán)可正可負(fù)。算法描述：（1）初始化：dis[u,v]=w[u,v]。（2）Fork=1tonFori=1tonForj=1tonIfdis[i,j]dis[i,k]+dis[k,j]ThenDis[i,j]=dis[i,k]+dis[k,j]。（3）算法結(jié)束：dis即為所有點(diǎn)對(duì)的最短路徑矩陣。算法小結(jié)：此算法簡(jiǎn)單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對(duì)于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。算法實(shí)現(xiàn)：見參考文獻(xiàn)[11]。七、Prim算法適用范圍：（1）用于求無向圖的最小生
語文相關(guān)推薦
鄂ICP備17016276號(hào)-1