【正文】 在 B我們找出 B 到 C(3 公里 )是最短的路徑。那么通過這個(gè)環(huán)路，環(huán)路中任意兩點(diǎn)的最短路徑就可以無(wú)窮小下去。 FloydWarshall 的原理是動(dòng)態(tài)規(guī)劃： 設(shè) Di,j,k 為從 i 到 j的只以 (1..k)集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長(zhǎng)度。 for (int k = 0。 // ( +j+ )。 ++w) if (length[v][w] length[v][u] + length[u][w]) { length[v][w] = length[v][u] + length[u][w]。 j row。// 任意兩點(diǎn)之間路徑長(zhǎng)度 int[][][] path = null。 break。 pnextarc=[i].firstarc。 scanf(%d,amp。 //找頂點(diǎn) V的第一條弧 while(p!=NULL) { if(visited[padjvex]==0) { dfs(g,padjvex,flag)。 for(i=0。 typedef struct VNode{ VertexType data。 while(pre[k]!=1) { printf(%d ,pre[k])。in。 j=i。in。 ：反復(fù)對(duì)邊集 E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集 V中的每個(gè)頂點(diǎn) v 的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行 |v|1 次） ：判斷邊集 E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。,x2=line[3]39。 break。 k) const{ //重載比較運(yùn)算符 return f 。 OPEN 表保存了所有已生成而未考察的節(jié)點(diǎn)， CLOSED 表中記錄已訪問過的節(jié)點(diǎn)。 ++i) dist[i] = maxint。 } int main() { freopen(, r, stdin)。 c[u][j]maxint) { int newdist = dist[u] + c[u][j]。 s[v] = 1。 include iostream using namespace std。但直到 1959 年荷蘭計(jì)算機(jī)科學(xué)家Edsger Wybe Dijkstra 才給出這一問題求解的基本方思想，并給出了算法。 本科畢業(yè)設(shè)計(jì) (論文 ) 題目名稱： 最短路徑算法的研究 學(xué) 院： 計(jì)算機(jī)科學(xué)技術(shù) 專業(yè)年級(jí)： 計(jì)算機(jī)科學(xué)與技術(shù)（師范 ） 08 級(jí) 學(xué)生姓名： 王超奇 班級(jí)學(xué)號(hào)： 2 班 13 號(hào) 指導(dǎo)教師： 劉錫祥 二○一二 年 六月 八日 I 摘 要 本文目的在于研究關(guān)于最短路徑的算法，為研究最短路徑問題在一些出行問題、管理問題、工程問題及實(shí)際生活問題中的應(yīng)用，為企業(yè)和個(gè)人提供方便的選擇方法。當(dāng)時(shí)的 Dijkstra 提出這一算法主要解決的問題是從固定的一個(gè)點(diǎn)到其他各點(diǎn)的最短路徑問題，后來(lái)這個(gè)算法就成了眾所周知的 Dijkstra 算法，也成了一代經(jīng)典。 const int maxnum = 100。 // 依次將未放入 S 集合的結(jié)點(diǎn)中，取 dist[]最小值的結(jié)點(diǎn)，放入結(jié)合 S 中 // 一旦 S 包含了所有 V中頂點(diǎn)， dist 就記錄了從源點(diǎn)到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度 // 注意是從第二個(gè)節(jié)點(diǎn)開始，第一個(gè)為源點(diǎn) for(int i=2。 if(newdist dist[j]) { dist[j] = newdist。 // 各數(shù)組都從下標(biāo) 1 開始 // 輸入結(jié)點(diǎn)數(shù) cin n。 for(int i=1。算法中有一步是根據(jù)估價(jià)函數(shù)重排 OPEN 表。 } }k。 } for(int i=0。a39。如果存在未收斂的頂點(diǎn)，則算法返回 false，表明問題無(wú)解；否則算法返回 true，并且從源點(diǎn)可達(dá)的頂點(diǎn) v 的最短距離保存在 d[v]中。i++) { dis[i]=MAXVALUE。 while(j!=1) { printf(%d ,j)。i++) { for(j=0。 k=pre[k]。 ArcNode *firstarc。in。 finished[padjvex ]=1。)。 [i].firstarc=p。 default:printf(輸入的操作碼錯(cuò)誤 \n\n)。// 任意兩點(diǎn)之間的路徑 public FLOYD(int[][] G) { int MAX = 100。 j++) spot[i][j] = 1。// 如果存在更短路徑則取更短路徑 spot[v][w] = u。 else { outputPath(spot, i, spot[i][j], onePath, point)。 k [i][j].length。 若最短路徑經(jīng)過點(diǎn) k，則 Di,j,k = Di,k,k1 + Dk,j,k1； 若最短路徑不經(jīng)過點(diǎn) k，則 Di,j,k = Di,j,k1。如果不處理這個(gè)負(fù)環(huán)路，程序就會(huì)永遠(yuǎn)運(yùn)行下去。如此然后去 C， 再到 D。 我們從 A 到 B， 然后設(shè)定 A和 B 之間的距離無(wú)限大。設(shè)想從我們可以從圖中找到一個(gè)環(huán)路（即從 v出發(fā)，經(jīng)過若干個(gè)點(diǎn)之后又回到 v）且這個(gè)環(huán)路中所有邊的權(quán)值之和為負(fù)。 FloydWarshall 算法的時(shí)間復(fù)雜度為 O(N^3)，空間復(fù)雜度為 O(N^2)。 (From + i + to + j + path is: )。 if (spot[i][j] == 1) onePath[point[0]++] = j。 w row。 i++) // 初始化為任意兩點(diǎn)之間沒有路徑 for (int j = 0。 算法具體分析 以無(wú)向圖 G 為入口，得出任意兩點(diǎn)之間的路徑長(zhǎng)度 length[i][j]，路徑path[i][j][k] Java 算法 途中無(wú)連接得點(diǎn)距離用 0 表示，點(diǎn)自身也用 0 表示 public class FLOYD { int[][] length = null。 case 3: done=0。 padjvex=j。 printf(請(qǐng)輸入邊數(shù)： )。 p=[v]. firstarc。 int dfs_topsort(ALGraph g,int n) { int flag=1,i。 }ArcNode。 k=i。 for(i=0。i++) { printf(%d %d\n,i,dis[i])。 for(i=0。 （ 1） 單源最短路徑 (從源點(diǎn) s 到其它 所有頂點(diǎn) v)； （ 2） 有向圖和無(wú)向圖 (無(wú)向圖可以看作 (u,v),(v,u)同屬于邊集 E 的有向圖 )； （ 3） 邊權(quán)可正可負(fù) (如有負(fù)權(quán)回路輸出錯(cuò)誤提示 )； （ 4） 差分約束系統(tǒng) 算法描述和算法實(shí)現(xiàn) 12 1,.初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值 d[v] ←+∞, d[s] ←0。139。 ==y2){ ans=。 bool operator (const knight amp。 如圖有如下的狀態(tài)空間：（起始位置是 A，目標(biāo)位置是 P，字母后的數(shù)字表示節(jié)點(diǎn)的估價(jià)值） 狀態(tài)空間圖 搜索過程中設(shè)置兩個(gè)表： OPEN 和 CLOSED。 i=n。 else cout que[i] endl。amp。 } dist[v] = 0。 4 具體算法分析 下 圖中的有向 圖，應(yīng)用 Dijkstra 算法計(jì)算從源頂點(diǎn) 1到其它頂點(diǎn)間最短路徑的過程列在下表中。 選題的國(guó)內(nèi)外動(dòng)態(tài) 最短路徑這一重要問題早在 20 世紀(jì)初就已經(jīng)得到人們的高度重視，當(dāng)時(shí)也有很多科學(xué)家研究這一問題的求解方法。同時(shí)，也為 其他的同學(xué) 提供一些解題的思路與方法，為 他們 提供有利的資源。 現(xiàn)如今比較流行的最短路徑規(guī)劃算法主要有以下三類：第一類是基于圖論理論的算法；第二類則是基于傳統(tǒng)人工智能理論的算法；第三類則是基于智能控制技術(shù)的算法。 const int maxint = 999999。 i=n。 prev[j] = u。 // 輸入路徑數(shù) cin line。 i=n。這樣循環(huán)中的每一步只考慮 OPEN 表中狀態(tài)最好的節(jié)點(diǎn)。 bool visited[8][8]。i8。,y2=line[4]39。 （ 1） PASCA 語(yǔ)言 For i:=1 to |V|1 do For 每條邊 (u,v)∈ E do Relax(u,v,w)。 pre[i]=1。 j=pre[j]。jn。 } coutendl。 }VNode,AdjList[MAXV ]。i++) //置初值 { visited[i]=0。 } p=pnextarc 。 printf(請(qǐng)輸入圖的所有頂點(diǎn)： )。 } return OK。 } } } 實(shí)現(xiàn)文件 include include include include include void main() { printf(圖的拓?fù)渑判?)。 int row = 。 for (int i = 0。// 把經(jīng)過的點(diǎn)加入 } for (int i = 0。 outputPath(spot, spot[i][j], j, onePath, point)。 k++) ([i][j][k] + )。 因此， Di,j,k = min(Di,k,k1 + Dk,j,k1 , Di,j,k1)。 而BellmanFord 算法具有分辨這種負(fù)環(huán)路的能力。所以 ， 此算法則總是選擇最短的路徑。假設(shè)我們一開始在 A， 比較 A 到其他點(diǎn)的 路徑長(zhǎng)度 ， 找出 A 到 B 是最短的路徑 (5 公里 )。 與 Dijkstra 算法不同的是，在 BellmanFord 算法中，邊的權(quán)值可以為負(fù)數(shù)。 FloydWarshall 算法（ FloydWarshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題。 j++) { ()。 } } } void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) {// 輸出 i // 到 j 24 // 的路徑的實(shí)際代碼， point[]記錄一條路徑的長(zhǎng)度 if (i == j) return。 ++v) for (int w = 0。 i row。 （ 3） 算法結(jié)束： dis 即為所有點(diǎn)對(duì)的最短路徑矩陣。 break。 p=(ArcNode*)malloc(sizeof(ArcNode))。)。 visited[v]=0。 18 int finished[MAXV]。 struct ArcNode *nextarc。i++) { printf(%d %d\n,i,dis[i])。 }