【正文】 ed[MAXV]。amp。 visited[v]=0。i++) if([i].data==m)return i。)。[i].firstarc=NULL。 p=(ArcNode*)malloc(sizeof(ArcNode))。 while(done){ printf(請輸入操作碼： )。 break。 此算法時間復雜度 O(V+E)，時間和編程復雜度低，如遇到符 合條件的題目(DAG)，推薦使用。 （ 3） 算法結(jié)束： dis 即為所有點對的最短路徑矩陣。 path = new int[row][row][]。 i row。 v row。 ++v) for (int w = 0。 j row。 } } } void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) {// 輸出 i // 到 j 24 // 的路徑的實際代碼， point[]記錄一條路徑的長度 if (i == j) return。 i++) for (int j = i。 j++) { ()。 算法具體的形式包括： 確定起點的最短路徑問題：即已知起始結(jié)點，求最短路徑的問題。 FloydWarshall 算法（ FloydWarshall algorithm）是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或負權(quán)的最短路徑問題。 Dijkstra 求單源、無負權(quán)的最短路。 與 Dijkstra 算法不同的是，在 BellmanFord 算法中，邊的權(quán)值可以為負數(shù)。城市越多 ,可能的路徑也越多。假設(shè)我們一開始在 A， 比較 A 到其他點的 路徑長度 ， 找出 A 到 B 是最短的路徑 (5 公里 )。加溫時 , 固體內(nèi)部粒子隨溫升變?yōu)闊o序狀 ， 內(nèi)能增大 ， 而緩慢降溫時 粒子漸趨有序 ， 在每個溫度上都達到平衡態(tài) ， 最后在常溫時達到基態(tài) ，內(nèi)能減為最小。所以 ， 此算法則總是選擇最短的路徑。這是解決 TSP問題的最簡便的算法。 而BellmanFord 算法具有分辨這種負環(huán)路的能力。若是斐波那契堆作優(yōu)先隊列的話，算法時間復雜度，則為 O（ V*lgV + E）。 因此， Di,j,k = min(Di,k,k1 + Dk,j,k1 , Di,j,k1)。 全局最短路徑問題：求圖中所有的最短路徑。 k++) ([i][j][k] + )。 for (int i = 0。 outputPath(spot, spot[i][j], j, onePath, point)。 path[i][j] = new int[point[0]]。// 把經(jīng)過的點加入 } for (int i = 0。 for (int u = 0。 for (int i = 0。 j row。 int row = 。矩陣D(n)的 i 行 j 列元素便是 i 號頂點到 j 號頂點的最短路徑長度，稱 D(n)為圖的 距離矩陣 ，同時還可引入一個后繼節(jié)點矩陣 path 來記錄兩點間的最短路徑。 } } } 實現(xiàn)文件 include include include include include void main() { printf(圖的拓撲排序 )。 printf(\n\n)。 } return OK。r++){ cinm。 printf(請輸入圖的所有頂點： )。char m,n。 } p=pnextarc 。 } void dfs(ALGraph g,int v,intamp。i++) //置初值 { visited[i]=0。//拓撲排序算法 void dfs(ALGraph g,int v,intamp。 }VNode,AdjList[MAXV ]。有 4個域 {u,v,w,next}； indgr[i]:頂點 i的入度； stack[]:棧； （ 2） 初始化 :top=0 (棧頂指針 )； （ 3） 將初始狀態(tài)所有入度為 0的頂點壓棧； （ 4） I=0 (計數(shù)器 )； （ 5） While 棧非空 (top0) do ①頂點 v 出棧；輸出 v；計數(shù)器增 1； ② For 與 v鄰接的頂點 u do a. dec(indgr[u])； b. If indgr[u]=0 then 頂點 u入棧； （ 6） EXIT(I=|V|)。 } coutendl。amp。jn。 15 for(i=0。 j=pre[j]。 } p=node[i].next。 pre[i]=1。 13 link *next。 （ 1） PASCA 語言 For i:=1 to |V|1 do For 每條邊 (u,v)∈ E do Relax(u,v,w)。 } return 0。,y2=line[4]39。 (s)。i8。a){ //manhattan 估價函數(shù) return (abs()+abs())*10。 bool visited[8][8]。 CLOSED=[O2, H3, C4, B4, A5] （ 7） 估算 P3，已得到解 。這樣循環(huán)中的每一步只考慮 OPEN 表中狀態(tài)最好的節(jié)點。 searchPath(prev, 1, n)。 i=n。 i=line。 // 輸入路徑數(shù) cin line。 tmp = prev[tmp]。 prev[j] = u。 // u 保存當前鄰接點中距離最小的點的號碼 tmp = dist[j]。 i=n。 i=n。 const int maxint = 999999。 算法描述和算法實現(xiàn) 如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路徑，則 v1→ v2→ v3 一定是 v1→ v3 的最短路徑。 現(xiàn)如今比較流行的最短路徑規(guī)劃算法主要有以下三類：第一類是基于圖論理論的算法；第二類則是基于傳統(tǒng)人工智能理論的算法；第三類則是基于智能控制技術(shù)的算法。 選題的目的 本文研究目的在于收集整理關(guān)于最短路徑的普遍算法，為研究最短路徑問題在一些出行問題、管理問題、工程問題及實際生活問題中的應用，為企業(yè)和個人提供方便的選擇方法。同時，也為 其他的同學 提供一些解題的思路與方法，為 他們 提供有利的資源。 最短路徑問題是圖論研究中 的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。 選題的國內(nèi)外動態(tài) 最短路徑這一重要問題早在 20 世紀初就已經(jīng)得到人們的高度重視，當時也有很多科學家研究這一問題的求解方法。 Dijkstra 一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用 OPEN, CLOSE 表的方式，這里均采用永久和臨時標號的方式。 4 具體算法分析 下 圖中的有向 圖，應用 Dijkstra 算法計算從源頂點 1到其它頂點間最短路徑的過程列在下表中。 // 圖的結(jié)點數(shù)和路徑數(shù) // n n nodes // v the source node // dist[ ] the distance from the ith node to the source node // prev[ ] the previous node of the ith node // c[ ][ ] every two nodes39。 } dist[v] = 0。 ++j) if((!s[j]) amp。amp。 int tmp = prev[u]。 else cout que[i] endl。 j=n。 i=n。 } Dijkstra(n, 1, dist, prev, c)。 如圖有如下的狀態(tài)空間：（起始位置是 A，目標位置是 P，字母后的數(shù)字表示節(jié)點的估價值） 狀態(tài)空間圖 搜索過程中設(shè)置兩個表： OPEN 和 CLOSED。 CLOSED=[B4, A5] （ 4） 估算 C4；取得搜有子節(jié)點，并放入 OPEN 表中； OPEN=[H3, G4, E5, F5, D6]。 bool operator (const knight amp。 a){ //判斷 knight 是否在棋盤內(nèi) if(0 || 0 || =8 || =8) return false。 ==y2){ ans=。 //23 表示根號 5 乘以 10 再取其 ceil = Heuristic(s)。139。 (k)。 （ 1） 單源最短路徑 (從源點 s 到其它 所有頂點 v)； （ 2） 有向圖和無向圖 (無向圖可以看作 (u,v),(v,u)同屬于邊集 E 的有向圖 )； （ 3） 邊權(quán)可正可負 (如有負權(quán)回路輸出錯誤提示 )； （ 4） 差分約束系統(tǒng) 算法描述和算法實現(xiàn) 12 1,.初始化：將除源點外的所有頂點的最短距離估計值 d[v] ←+∞, d[s] ←0。 struct oo *next。 for(i=0。 while(p) { if(plen+dis[i]dis[pnum]) {dis[pnum]=plen+dis[i]。i++) { printf(%d %d\n,i,dis[i])。 int graph[MAX][MAX],n。 for(i=0。 } for(j=0。 k=i。 （ 1） AOV 網(wǎng) (Activity On Vertex Network)； （ 2） 有向圖； （ 3） 作為某些算法的預處理過程 (如 DP)。 }ArcNode。 status Creat_Graph1(ALGraph amp。 int dfs_topsort(ALGraph g,int n) { int flag=1,i。in) { if(visited[i]==0) { i++。 p=[v]. firstarc。 return ERROR。 printf(請輸入邊數(shù)： )。} printf(請輸入圖的所有邊，如 AB邊記為 AB，： \n)。 padjvex=j。 20 scanf(%d,amp。 case 3: done=0。還有，此算法的步驟（ 3） 可以在 toposort 中實現(xiàn)，這樣即減小了此算法復雜度的一個系數(shù)。 算法具體分析 以無向圖 G 為入口，得出任意兩點之間的路徑長度 length[i][j]，路徑path[i][j][k] Java 算法 途中無連接得點距離用 0 表示，點自身也用 0 表示 public class FLOYD { int[][] length = null。 for (int i = 0。 i++) // 初始化為任意兩點之間沒有路徑 for (int j = 0。 ++v) for (int w = 0。 w row。 j++) { point[0] = 0。 if (spot[i][j] == 1) onePath[point[0]++] = j。 j 。 (From + i + to + j + path is: )。 確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。 FloydWarshall 算法的時間復雜度為 O(N^3)，空間復