【正文】 AOV 網 (Activity On Vertex Network)； （ 2） 有向圖； （ 3） 作為某些算法的預處理過程 (如 DP)。這種操作在有關工程進度 /次序規(guī)劃之類問題中有著大量的應用。 } return true。 k=pre[k]。 k=i。in。dis[j]dis[i]+graph[i][j]) return false。j++) if(i!=jamp。 } for(j=0。dis[j]dis[i]+graph[i][j]) { dis[j]=dis[i]+graph[i][j]。j++) if(i!=jamp。i++) { for(j=0。 for(i=0。 pre[i]=1。in。 int i,j,k。 int graph[MAX][MAX],n。 } //這個是鄰接矩陣 const int MAX = 100。 } coutendl。 while(j!=1) { printf(%d ,j)。i++) { printf(%d %d\n,i,dis[i])。 } } for(i=0。 while(p) { if(plen+dis[i]dis[pnum]) 14 return false。} p=pnext。 while(p) { if(plen+dis[i]dis[pnum]) {dis[pnum]=plen+dis[i]。in。 } dis[s]=0。i++) { dis[i]=MAXVALUE。 for(i=0。 int i,j。 } graph。 typedef struct { int num。 struct oo *next。amp。 For 每條邊 (u,v)∈ E do If dis[u]+wdis[v] Then Exit(False) （ 2） C/C++語言 void bellman_ford(int v) { for 1 to n initialize dist[v]。如果存在未收斂的頂點，則算法返回 false，表明問題無解；否則算法返回 true，并且從源點可達的頂點 v 的最短距離保存在 d[v]中。 （ 1） 單源最短路徑 (從源點 s 到其它 所有頂點 v)； （ 2） 有向圖和無向圖 (無向圖可以看作 (u,v),(v,u)同屬于邊集 E 的有向圖 )； （ 3） 邊權可正可負 (如有負權回路輸出錯誤提示 )； （ 4） 差分約束系統(tǒng) 算法描述和算法實現(xiàn) 12 1,.初始化：將除源點外的所有頂點的最短距離估計值 d[v] ←+∞, d[s] ←0。對圖 G 運行 BellmanFord算法的結果是一個布爾值，表明圖中是否存在著一個從源點 s 可達的負權回路。 } BellmanFord 算法 算法介紹及適用條件和范圍 BellmanFord 算法能在更普遍的情況下（存在負權邊）解決單源點最短路徑問題。 printf(To get from %c%c to %c%c takes %d knight moves.\n,line[0],line[1],line[3],line[4],ans)。 (k)。 =x1,=y1,==0,=Heuristic(k),=+。139。a39。139。a39。 } } } } int main(){ char line[5]。 = + 1。 //23 表示根號 5 乘以 10 再取其 ceil = Heuristic(s)。amp。i++){ =+dirs[i][0],=+dirs[i][1]。 } for(int i=0。 ==y2){ ans=。 if(==x2 amp。 } void Astar(){ //A*算法 knight t,s。 } int Heuristic(const knight amp。 a){ //判斷 knight 是否在棋盤內 if(0 || 0 || =8 || =8) return false。//8個移動方向 priority_queueknight que。 //已訪問標記 (關閉列表 ) int x1,y1,x2,y2,ans。 } }k。 bool operator (const knight amp。 struct knight{ int x,y,step。 具體算法分析 在國際象棋的棋盤上，一匹馬共有 8 個可能的跳躍方向，求從起點到目標點之間的最少跳躍次數(shù) 。 CLOSED=H3C4, B4, A5] （ 6） 估算 O2，取得搜有子節(jié)點，并放入 OPEN 表中； OPEN=[P3, G4, E5, F5, D6]。 CLOSED=[B4, A5] （ 4） 估算 C4；取得搜有子節(jié)點，并放入 OPEN 表中； OPEN=[H3, G4, E5, F5, D6]。 （ 2） 估算 A5，取得搜有子節(jié)點，并放入 OPEN 表中； OPEN=[B4, C4, D6]。 9 算法描述和算法實現(xiàn) 算法描述及其實現(xiàn) （ 1） 初始狀態(tài)： OPEN=[A5]。算法中有一步是根據(jù)估價函數(shù)重排 OPEN 表。 如圖有如下的狀態(tài)空間：（起始位置是 A，目標位置是 P，字母后的數(shù)字表示節(jié)點的估價值） 狀態(tài)空間圖 搜索過程中設置兩個表： OPEN 和 CLOSED。 因此， A*算法只 要求產生問題的全部狀態(tài)空間的部分結點，就可以求解問題了，搜索效率較高。 } 輸入數(shù)據(jù) : 5 7 1 2 10 1 4 30 1 5 100 2 3 50 3 5 10 4 3 20 4 5 60 輸出數(shù)據(jù) : 999999 10 999999 30 100 10 999999 50 999999 999999 999999 50 999999 20 10 30 999999 20 999999 60 8 100 999999 10 60 999999 A* 算法 算法介紹及適用條件和范圍 A*（ AStar）算法是一種靜態(tài)路網中求解最短路徑最有效的方法； 公式表示為 ： f(n)=g(n)+h(n), 其中 f(n) 是從初始點經由節(jié)點 n 到目標點的估價函數(shù)， g(n) 是在狀態(tài)空間中從初始節(jié)點到 n 節(jié)點的實際代價， h(n)是從 n 到目標節(jié)點最佳路徑的估計代價 A*算法屬于一種啟發(fā)式搜索。 // 路徑 cout 源點到最后一個頂點的路徑為 : 。 } Dijkstra(n, 1, dist, prev, c)。 ++j) printf(%8d, c[i][j])。 ++i) { for(int j=1。 for(int i=1。 i=n。 // p 指向 q c[q][p] = len。 ++i) { 7 cin p q len。 for(int i=1。 j=n。 i=n。 int p, q, len。 // 各數(shù)組都從下標 1 開始 // 輸入結點數(shù) cin n。 else cout que[i] endl。 i=1。 } que[tot] = v。 tot++。 int tmp = prev[u]。 que[tot] = u。 } } 6 } } // 查找從源點 v 到終點 u 的路徑，并輸出 void searchPath(int *prev,int v, int u) { int que[maxnum]。 if(newdist dist[j]) { dist[j] = newdist。amp。 j=n。 } s[u] = 1。 dist[j]tmp) { u = j。 ++j) if((!s[j]) amp。 // 找出 當前未使用的點 j 的 dist[j]最小值 for(int j=1。 ++i) { int tmp = maxint。 // 依次將未放入 S 集合的結點中，取 dist[]最小值的結點，放入結合 S 中 // 一旦 S 包含了所有 V中頂點， dist 就記錄了從源點到所有其他頂點之間的最短路徑長度 // 注意是從第二個節(jié)點開始，第一個為源點 for(int i=2。 } dist[v] = 0。 // 初始都未用過該點 if(dist[i] == maxint) prev[i] = 0。 ++i) 1 2 5 3 4 10 50 100 20 10 30 60 5 { dist[i] = c[v][i]。 // 判斷是否已存入該點到 S 集合中 for(int i=1。 // 圖的結點數(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。 // 記錄當前點 的前一個結點 int c[maxnum][maxnum]。 // 各數(shù)組都從下標 1 開始 int dist[maxnum]。 const int maxnum = 100。 4 具體算法分析 下 圖中的有向 圖，應用 Dijkstra 算法計算從源頂點 1到其它頂點間最短路徑的過程列在下表中。S={s}； （ 2） For i:=1 to n ①取 VS中的一頂點 u使得 dis[u]=min{dis[v]|v∈ VS} ② S=S+{u} ③ For VS 中每個頂點 v do Relax ? ?, , ,uu vW v （ 3）算法結束： dis[i]為 s到 i的最短距離； pre[i]為 i的前驅節(jié)點。 v2→ v3→ v4 一定是 v