第1章需求分 第2章動態規劃方法的介 第3章基本理論知識和方 第4章實驗分 參考文 附錄設計系統部分源代 1求分在的實際生活中常常會出現這樣的問題：倆個城市之間，是否有道路可通,在有多條通路的情況下，哪一條總程最短；在公路中，即從某一城市出發，途中必須經過哪幾個城市才會使花費的總代價最少。通常近距離時可以憑經驗或者作出判斷，但若倆個城市相距較遠且中間又有多條通路，又如何作出判斷呢？這時可以一個簡單的程序建立一個交通咨詢系統，作出最優決策。在這個系統中，可以把地圖模型化為一個圖，結點表示一段公路的起點和終點，邊的權值表示公路的長度，的目標是從起點出發找到一條到達2態規劃方法的介將交通網絡圖視為帶權有向本文中只對倆個城市之間的距離進行）有向圖G，然后將這個賦權網絡圖輸入到計算機組中（n表示城市的個數。定義帶權有向定義①若圖G=G(V,E)中各邊e都賦有一個實數W(e),稱為邊e的權,則稱這種圖為賦權圖,G=G(V,E,W)G=G(V,E)

We

,eEG,u是vi到vj1Wu的權則稱Wu為u的長長最小的i到vj的路Wu稱為最短路徑。nui到vn的通路u使全長最短即 We迪杰斯特拉算法流城市之間最短路徑（城市之間最短路徑（dijkstra算法2-1dijkstra算法計算最短路弗洛伊德算法流n次，這樣便可求得由用戶由用戶城市之間最短路徑（floyd算法最后求的從起點城市到最后求的從起點城市到終點城市的最短路徑的間經過的城市和從起點城市到途經2-4-1floyd3本理論知識和方最短路基本介60年代以前就卓有成效了其中對賦權圖j0有效算法是由荷蘭著名計算機Dijsta在1959年首次該算法能夠解決兩指點間的最短路G中一特定點到其它各頂點的最短路徑。DijkstraFordFord算法,但在現實生活中 在wijDijkstra基本定

定義①若圖G=G(V,E)eW(e),e的權,則稱這種圖為賦權圖,G=G(V,E)

We

,eEG,u是vi到vj的路Wu的權,Wu為u的長,長最小的vi到vj的路Wu若要找出從vi到vn的通路u,使全長最短,即minWuWe 迪杰斯特拉算基本定一般的表述通常有兩種方式，一種用和臨時標號方式，一種是用OPEN,CLOSE表的方式，這里均采用和臨時標號的方式。基本原DDvD[3]=2v32。這里強調相對就是說在算法過程中D的值是在不斷近最終結果但在過程中不一定就等于最短路徑長度。vviDD為∞。顯然，長度為D[j]=Min{D|vi∈V}v(v,vj)。那么，vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)vvkD[j]和從vjvkS為已求得最短路徑的終點的集合，則可證明：下一條最短路徑（X）或者是弧(v,x)S中的頂點而最后XD[j]=Min{D|vi∈V-S}其中，D或者是弧(v,vi)D[k](vk∈S)和弧(vk,vi)上的權值之和。迪杰斯特拉算MAXCOSTSvv出發到圖上其viD=arcs[LocateVex(G,v),i]vi∈V2）vj，D[j]=Min{D|vi∈V-S3）vV-Svk可達的最短路徑長度。G=(V,E)EwV0到其余各點的最短思想內V0SV0T中任何頂點的最短路SV0TV0SV0到TVkV0Vk的直接路徑的權值；或是V0SVk的路徑權值之和（反證法可證弗洛伊德算基本定n次，這樣便可求得基本原costvivjvivj存cost[i][j]n次試探。首先考慮vivj1v2,即如果（vi,…,v2）和（v2,…,vj）1vi,..,v2,…,vjvivj2的最短路徑。vivj12v3,n次比較，vivj的最短路徑。按此方法，可以同時求得各對頂點間的最短路徑。n階方陣序列：A(0),A(1),…,A(n)從上述計算公式可見，A(1)[i][j]vivj1A(n)[i][j]vivj倆種算法的比從算法的基本思想而言，Dijkstra算法的基本思想是以Vs為起點,從圖中找出與其距離最短的頂點。假設該點為Vi,然后再以Vi作為參照點,從余下的頂點中找出與其距離最短的頂點,依次類推直到所有的頂點都對比完為止至止,Vs到各頂點的最短距離就已經求出來了。至于具體的最短路徑,常用的方法是“反向追蹤法。即從終點出發,“順藤摸瓜”找到最短距離上的各個點,按照有向圖的方向,就可以得到最短路徑。Floyd算法的基本思想是:從Vs到Vt的最短路徑是以下各種可能路徑中的長度最小的那條。若<Vs,Vt>存在,則存在路徑{Vs,Vt}。(路徑中不含有其它頂點) 若<Vs,V1>,<V1,Vt>存在,則存在路徑{Vs,V1,Vt}。(路徑中所含頂點序號不大于1) 若<Vs,V2>,<V2，Vt>存在,則存在一條最短路徑{Vs,?V2?Vj}(路徑中所含頂點序號不大于2)依次類推,則Vs到Vt的最短路徑應是上述這些路徑中路徑長度最小者。兩種算法的基本思想不同,導致了兩種算法結果的不同對于Dijkstra算法而言,其結果是可求出從某一個頂點到其余各頂點的最短路徑。而Floyd算法的結果是可以得出圖中任意兩對頂點之間的最短路徑。而從算法步驟而言，Floyd算法是從鄰接矩陣出發,而且最短路徑可以從序號矩陣中找出來。最短路徑的權值從距離矩陣中得出。在許多情況下,圖中的權重可能是負值。Dijkstra算法要求每一個權重必須大于或等于零,這是該算法Floyd算法計算最短路徑時間4驗分4.1結隨機選擇6個城市作為一個交通系統，這6個城市分別為：長春，哈爾濱，，G4-14-2在c語言中，把這些城市的信息用一個c結構體數組（city[][]）來保存typedef{charname[99];charnum;intn*n2（n表示城市的個數2G(INF表示無窮，即倆個城市之間沒有通路4-3g[6][6]2city4-4程序運行圖迪杰斯特拉算法案算法步S={V0},T={其余頂點}，T中頂點對應的距離值TWSTWV0Vi的距離值縮短，2、3SW=Vi流程out函數，獲取dis[][]4-5dijkstra算法流分析，調4-6程序運行圖305060注：此處的最短距離是指從起點城春到各個頂點城市的最短距離；弗洛伊德算法案算法步uvwuwv比已知的GViVjG[i,j]=d，d表示該路的長度；否則G[i,j]=無窮大。定義一個矩陣D用來記錄所點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。把各個頂點圖中，比較插點后的距離與原來的距離，G[i,j]=D中則包含了最短通路徑的信息。V5V1DD(5,1)=3V5V1V3，路徑為{V5,V3,V1}D(5,3)=3V5V3D(3,1)=1V3V1流程4-7floyd分析，調4-8程序運行圖305060注：此處的最短距離是指從起點城春到各個頂點城市的最短距離；結花費變得最少。對于實際的交通網絡圖，可以把城市之間的信息于數據庫中，通過對于對于最短路徑算法，不僅可以用于出行的計算，還可以用 地圖等網絡地圖的應搶修、交通指揮、GPS導航等行業應用中使用的非常廣泛，同時最短路徑也是圖論研究中的題可以通過圖的相關知識來解決，特別是在解決最短路徑問題中，顯得尤為重要。參考文1刁在筠，，宿潔，[M].：高等教育2譚浩強.C語言程序設計[M].：3謝金星，邢文訓.網絡優化[M].：4嚴蔚敏，吳偉民.數據結構（c語言版）[M].：5、主編《圖論及其算法，中國科學技術大學，2005年6熊偉，運籌學，第二版，：機械工業，20117，數學建模基礎，第二版，：科學，20118韓中庚宋明武邵廣紀，數學建模競賽獲獎精選與點評，：科學，2007計系統部分源代C語言（1）intd[100],path[100],final[100];inttypedef{charname[99];charnum;intvoiddijkstra(ints,intn)//{inti,j,k,mi;{}{intmin=999;{}{}}}voidout(ints,intn)//{intb[100];//bs到某頂點的最短路徑上的各個頂點的編點，從后向前inti,j,p,m;{printf("從起點城市%d到頂點城市%d不存在路徑{//printf("從源點%d到頂點%d的最短路徑長度為：%d\n",s,i,d[i]);{}for(j=m;j>=0;j--{}}}}{ints,n=6;inti,j;charfrist;charcityc[100];strcpy(c[1].name,"哈爾濱strcpy(c[2].name,"strcpy(c[3].name,"沈陽strcpy(c[4].name,"石家莊printf("請選擇起點城市和終點城春（A，哈爾濱(B),（C，沈陽(D)，石家(E)，太原scanf("%c%c",&frist,&last);{{printf("您選擇的起點城市是%s，終點城市是}}for(intx=0;x<n;x++)for(inti=0;i<n;i++)printf(":%d,:%s}2：#defineINF99999typedef{charname[99];charnum;intint{intintn,i,j,k;intintdis[10][10];charfrist;charlast;cityc[100];strcpy(c[0].name,"長春strcpy(c[1].name,"哈爾濱strcpy(c[2].name,"strcpy(c[3].name,"沈陽strcpy(c[4].name,"石家莊printf("請選擇起點城市和終點城春（A，哈爾濱(B),（C，沈陽(D)，石家