畢業(yè)論文--開放最短路徑優(yōu)先協(xié)議(ospf)路徑選擇算法

1、書 明 說 計 設課程名稱：數(shù)據(jù)結構設計題冃開放最短路徑優(yōu)先協(xié)議(ospf)路徑選擇算法計算機科學與信息工程系學生姓名學 號專業(yè)班級指導教師王振鋒200803030022網(wǎng)絡一班2010 年 6 h 19 日課程設計任務書設計題目開放最短路徑優(yōu)先協(xié)議（ospf）路徑選擇算法學牛姓名王振鋒所在院系專業(yè)、年級、班08網(wǎng)絡工程一班設計要求：實現(xiàn)以下幾個功能1、實現(xiàn)圖的建立；2、用鄰接矩陣存儲圖的信息；3、用不同的算法實現(xiàn)在已建圖中最短路徑的選擇；4、輸出最短路徑的權值和相應的路徑。學生應完成的工作：（1）根據(jù)課程設計要求，分析思路并構建模型，劃分子模塊、完善其功能；（2）根據(jù)各模塊的功能設計并編寫程

2、序段、連接各程序段使之形成一個有機的整體；（3）調試、運行程序進而得到正確的結果；（4）根據(jù)實驗設計運行過程，寫出實驗論文并總結實驗教訓。參考文獻閱讀：數(shù)據(jù)結構程序設計（蘇仕華等，機械工業(yè)岀版社）；數(shù)據(jù)結構（吳偉民等c語言版，清華大學出版社）；c+程序設計導學（李春葆等 清華大學出版社）；tcp/ip協(xié)議原理與應用（第3版）查普爾（laura a.chappell）（美國）蒂特爾（ed title） 譯者:張長富出版社:清華大學出版社tcp/ip 協(xié)議詳解（三卷本）（w. richard stevens）.工作計劃：（1） 2010. 6. 7 -9分析課程題目設計要求，構建模型，劃分子模塊進

3、行分工合作；（2）2010. 6. 10 - 13根據(jù)設計要求和模塊寫出各部分相應的程序代碼；（3）2010.6. 14 -15組合并調試程序，得到相應的實驗結果；（4）2010.6.16 -19根據(jù)設計過程寫出實驗論文并總結任務下達日期：2010年 6月5日任務完成日期：2010年 6月5 f1指導教師（簽名）：學主（簽名）：開放最短路徑優(yōu)先協(xié)議(ospf)路徑ra摘要:ospf 采用 spf (shortest path first)算法(也叫做 dijkstra 算法，spf 算法是鏈路狀態(tài)型算法，鏈路狀態(tài)型算法對自己以及其它路由器產(chǎn)生的鏈路狀態(tài)信息 進行匯總，在本地生成一個鏈路狀態(tài)數(shù)據(jù)

4、庫，來對此數(shù)據(jù)庫進行運算，從而得到一 張以自己為根的、到達其它各目的節(jié)點最近的一張路徑圖，根據(jù)算法和協(xié)議特點, 這張圖是無環(huán)路的。本次課程設計是模擬最短路徑優(yōu)先協(xié)議(ospf)路徑選擇算法，使用鄰接矩陣存儲圖的有關信息，用迪杰斯特拉(dijkstra)算法得出最短路徑，并附有弗洛伊德(floyd)算法加以比較。另為了更好的對dijkstra算法和floyd算法有更好的理解在對其又做了改進使其能生成多源結點到多結點的最短路徑及相應的最短路 徑的權值。關鍵詞:最短路徑算法c語言 最短路徑優(yōu)先協(xié)議(ospf) 迪杰斯特拉(dijkstra) 弗洛伊德(floyd) 最短路徑算法 圖 鄰接矩陣最短路徑

5、長度權值(cost)1課程設計背景612課程設計要求62. 設計方案82.1最短路徑算法的分類82.2 dijkstra 算法的基本原理82.3 dijkstra算法的步驟93 方案實施113.1實驗程序的整體框架113.2算法核心代碼實現(xiàn)113. 2. 1 di jkstra 算法白勺實現(xiàn)11322列洛伊德（floyd）算法實現(xiàn)143.2.3鄰接矩陣的的創(chuàng)建154. 結果與結論214.1設計內容214.2課程設計程序源程序214.3程序輸出圖344.3.1程序主界面344.3.2用迪杰斯特拉（dijkstra）算法處理已儲存的路由圖354.3.3用floyd算法處理已儲存的路由圖結果3643

6、4設計結果分析374.3.5課程設計總結375. 收獲與致謝376. 參考文獻387. 附件381. 課程設計背景11課程設計目的木次課程設計我門要在vc+環(huán)境的最短路徑，常用得有dijkstra算法和floyd 算法等，這次主要應用dijkstra算法并附有floyd算法加以比較完成課程設計。 dijkstra（迪杰斯特拉）算法是典型的最短路徑路由算法，用丁計算一個節(jié)點到其他 所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點 為止。dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多， 所以效率低。dijkstra算法是很有代表性的最短路算法，在很多

7、專業(yè)課程屮都作 為基本內容有詳細的介紹，如通信有原理，圖論，運籌學等等。通過本次通過這次課程設計，我們要對上課所學得知識進行鞏固，掌握圖、子 圖、結點的度數(shù)、有向圖、無向圖、多重圖、完全圖、補圖、生成了圖、圖的同構、 路、回路、連通圖、弱連通、強連通等概念及其性質；掌握圖的拒陣表示，給定圖 的鄰接矩陣會求任一結點的入度、出度和度數(shù)；一個結點到另一個結點長度為k的 路徑的條數(shù)；該圖的可達性矩陣。對最小生成樹、最短路徑、dijkstra算法，最短路由冇了更深得理解。本次 課程實驗，要了解最短得路由得算法，掌握dijkstra算法，floyd-warshall算法 等算法得概念，基本原理和思想。加深

8、對數(shù)據(jù)結構這門課程的理解，并11在vc+ 環(huán)境下進行運行，得到輸出結果圖，并對圖進行結果與分析。1. 2課程設計要求根據(jù)所學數(shù)據(jù)結構基礎知識，使用迪杰斯特拉（dijkstra）算法，編寫一 c程 序，它能根據(jù)讀入得帶權有向圖g的數(shù)據(jù)，構造并輸出圖g的頂點vi到其它毎個 頂點的最短路徑及長度，并輸出其最短路徑。并附冇弗洛伊徳（floyd）算法和迪 杰斯特拉（dijkstra）算法相比較，兩算法有何不同？設計具體要求：實現(xiàn)以下幾個功能：（1）、實現(xiàn)圖的建立;（2）、用鄰接矩陣存儲圖的信息；（3）、用不同的算法實現(xiàn)在已建圖屮最短路徑的選擇（4）、輸出最短路徑的權值和相應的路徑。1. 3運行環(huán)境該程序

9、的運行環(huán)境為windows xp系統(tǒng),microsoft visual c+60版本。2. 設計方案2.1最短路徑算法的分類所謂最短路徑(shortest path)問題指的是：如果從圖中某頂點出發(fā)(此點 稱為源點)，經(jīng)圖的邊到達另一頂點(稱為終點)的路徑不止一條，如何找到一條 路徑使沿此路徑上各邊的權值z和為最小。設一有向網(wǎng)絡g= (v,e),已知各邊的 權值，并設每邊的權均大于零，以某指定v0為源點，求從v0到圖的其余各點的最 短路徑。用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作 “路徑算法”。最常用的路徑算法有：(1) dijkstra 算法(2) a*算法(3) sp

10、fa 算法(4) bel iman-ford 算法(5) floyd-warshall 算法(6) johnson 算法2.2 dijkstra算法的基本原理dijkstra算法是由荷蘭計算機科學家艾茲格迪科斯徹發(fā)現(xiàn)的。算法解決的是有 向圖中最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著 城市間開車行經(jīng)的距離。dijkstra算法可以用來找到兩個城市之間的最短路徑。這 個算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。 初始時，源點s的路徑長度值被賦為o(ds=o),同時把所有其他頂點的路徑長度 設為無窮大，即表示我們不知道任何通向這些頂點的路徑(對于

11、v屮所有 頂點v 除s夕卜dv=oo)。當算法結束時，dv中儲存的便是從s到v的最短路徑，或者如 果路徑不存在的話是無窮大。dijstra算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那么從s到 u的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到v的路徑。這條路徑 的長度是du+w(u,v)。如果這個值比口前已知的dv的值要小，我們可以用新值來 替代當前dv中的值。拓展邊的操作一直執(zhí)行到所冇的dv都代表從s到v最短路 徑的花費。這個算法經(jīng)過組織因而當du達到它最終的值的吋候每條邊(u,v)都只被 拓展一次。算法維護兩個頂點集s和q。集合s保留了我們己知的所有dv的值已 經(jīng)是最短

12、路徑的值頂點，而集合q則保留其他所冇頂點。集合s初始狀態(tài)為空，而 后每一步都有一個頂點從q移動到so這個被選擇的頂點是q中擁有最小的du 值的頂點。當一個頂點u從q中轉移到了 s中，算法對每條外接邊(u,v)進行拓展。2.3 dijkstra算法的步驟dijkstra算法的基本思路是：假設每個點都有一對標號(dj,內)，其屮dj是從起 源點s到點j的最短路徑的長度(從頂點到其本身的最短路徑是零路(沒冇弧的路)， 其長度等于零)；pj則是從s到j的最短路徑屮j點的前一點。求解從起源點s到點j 的最短路徑算法的基本過程如下：初始化。起源點設置為：ds=0, ps為空;所冇其他點:di=co, pi

13、=?;標記起源點s, 記k二s,其他所有點設為未標記的。(2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置岫 是從點k到j的直接連接距離。(3) 選取下一個點。從所有未標記的結點中，選取dj中最小的一個i： dj=min dj, 所冇未標記的點j點i就被選為最短路徑屮的一點，并設為已標記的。(4) 找到點i的前一點。從已標記的點屮找到直接連接到點i的點幾作為前一 點,設置：i=j*(5) 標記點i。如果所有點已標記，則算法完全推出，否則記k=i,轉到2)再繼 續(xù)。具休流程圖如圖1所示是預處理：拓撲檢查|當前節(jié)點齡接點加入到憂先隊列弄排京輸出結果取列中4個節(jié)點出隊原節(jié)點權值較

14、小圖1 dijkstra算法流程圖3. 方案實施3.1實驗程序的整體框架本次實驗的具體結構框架安排如下：(1) "dijkstra. h"模塊此模塊功能是實現(xiàn)dijksta算法選擇最短路徑，用函數(shù)void shortestpath dtj ( node a , status i , status vo , status *d , status *pre ) 計算圖a中所有頂點的最短路徑,另外并用函數(shù)void show (status *d , status *pre , int i , int vo)顯示最短路徑長度及相應的最短路徑。(2) . ” floyd, h” 模塊

15、此模塊的主要功能是實現(xiàn)floyd算法選擇最短路徑，用函數(shù)void floydl (node g, int num, path &p, dist d)計算圖g中所有頂點的最短路徑, 另外并用函數(shù) void output_pd(node g, int num, path p, dist d)顯示最短路徑 長度及相應的最短路徑。(3) . " main, cpp” 模塊此模塊主要實現(xiàn)鄰接矩陣的創(chuàng)建，從輸入的圖中提取信息并將其存儲到 創(chuàng)建的鄰接矩陣中，并在此模塊中用函數(shù)控制程序的運行及相關函數(shù)的 調用。3.2算法核心代碼實現(xiàn)3. 2. 1dijkstra算法的實現(xiàn)從上面可以看出，在按

16、標記法實現(xiàn)dijkstra算法的過程中，核心步驟就是從 未標記的點中選擇一個權值最小的弧段。這是一個循環(huán)比較的過程，如果不采用任 何技巧，未標記點將以無序的形式存放在一個鏈表或數(shù)組屮。那么要選擇一個權值 最小的弧段就必須把所有的點都掃描一遍，在大數(shù)拯量的情況下，這無疑是一個制 約計算速度的瓶頸。要解決這個問題，最冇效的做法就是將這些要掃描的點按英所 在邊的權值進行順序排列，這樣每循環(huán)一次即可取到符合條件的點，可大大提高算 法的執(zhí)行效率。另外，gis中的數(shù)據(jù)(如道路、管網(wǎng)、線路等)要進行最短路徑的計 算，就必須首先將其按結點和邊的關系抽象為圖的結構，這在gis中稱為構建網(wǎng)絡 的拓撲關系（由于這里

17、的計算與面無關，所以拓撲關系屮只記錄了線與結點的關系 而無線與面的關系，是不完備的拓撲關系）。如果用一個矩陣來表示這個網(wǎng)絡，不但 所需空間巨大，而且效率會很低。下而主要就如何用一個簡潔高效的結構表示網(wǎng)的 拓撲關系以及快速搜索技術的實現(xiàn)進行討論。網(wǎng)絡在數(shù)學和計算機領域中被抽象為圖，所以其基礎是圖的存儲表示。一般而言， 無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表 示。圖1帶權有向圖具體的實現(xiàn)代碼如下：void shortestpath_dlj ( node a , status i , status vo , status *d , status *prc )/a是傳

18、進的矩陣，i是結點數(shù)，vo是最短路徑的源結點int v, w, j, 1=1;status *final;/設置 int 扌旨針status min;final= (status *)malloc( sizcof(status)*i );/分配空間for (v=0; v<i; v+) /初始化finalv=false; prev二false;dv=avo v;if(dv< 10000)/找到頭結點 prev=v0;for (v=0;v<i;v+)if( av0v>=10000 )1+；if (1>1)printf (，zn從路由d岀發(fā)沒有最短路徑到其他端點！n,

19、vo+l); exit (0);/v0是一個孤立的頂點嘰v0=0;finalvo=true;for( j二0 ; j<i ; +j )min=maxnum;for ( w二0 ; w<i ; w+)if ( !final w )/判斷是否已被最短路徑路過if ( dw<min )v=w;min二dw; 找出最短的路徑finalv=true;3.2.2弗洛伊德(floyd)算法實現(xiàn)c=jfor ( w二0 ; w<i ; w+ )if(finalw && ( (min+avw)<dw)dw=min+avw;prew=v;洛伊德算法仍然使用圖的鄰接矩陣

20、arcsn+ln+l存儲帶權有向圖。算法的基 本思想是:設置一個nxn的矩陣a(k),其中除對角線的元索都等于0外，其它元索 a(k)iljl«示頂點i到頂點j的路徑長度，k表示運算步驟。開始時，以任意兩個頂 點之間的有向邊的權值作為路徑長度，沒有有向邊時，路徑長度為oo,當k=0時,a (o)ij=arcsij,以后逐步嘗試在原路徑中加入其它頂點作為中間頂點，如果增加 中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修 改矩陣元索。具體代碼如下：void floydl(node g, int num,path &p, dist d)long i, j,

21、 k, 1, b;/*初始化*/for (i二0;i<num;i+)for (j=0;j<num;j+)dij二 gij;if (i!=j && dij<finity ) /i 與 j 之間有路徑可通1=0;pi j 1+二i；pi j 1+二j；pi j 1+二t；else pi j 0二t ;for (k=0;k<num;k+)/遞推求解每一對頂點間的最短距離for (i=0;i<num;i+)for (j=0;j<num;j+)if (dij>dik+dkjj)di j二di k+dk j;/刷新距離for(l二0;pi k 1

22、!=t;l+)/pi k 1 !=-1 表示 i, k 間有通pi j 1二pi k 1;/把i, k間的路徑賦給i, j間的路徑 for(b=l;pk j b u-l;b+)pi j 1+二pk j b;/把 k, j 間的路徑給 i, j 間的路pijl=-l;/ffi 噺路徑；3. 23鄰接矩陣的的創(chuàng)建圖的數(shù)組表示也稱圖的鄰接矩陣存儲，它的基本思想是，將圖的頂點存放在一 維數(shù)組里，我們稱這個一維數(shù)組為頂點向量；用二維數(shù)組存儲頂點z間的關系，這 個二維數(shù)組即是鄰接矩陣，鄰接矩陣存儲的是邊或弧的信息。用鄰接矩陣表示圖的 優(yōu)點是，容易判斷任意兩個頂點間是否冇邊或弧相連，并容易求得各個頂點的度。

23、 具體建立步驟如下：(1) 聲明結構typedef status * node;用以存放圖的信息(2) 用函數(shù) a= (node) malloc ( num * sizeof (status *);開辟一個一維數(shù) 組空間(3) 用函數(shù) a訂二(status *) mal loc( num * sizeof (status);開辟一個二 維數(shù)組的空間用以存放邊的權值具體的實現(xiàn)函數(shù)如下(1) node build (status num )函數(shù)儲存自己建立的圖的信息node build (status num ):int i, j, k;node a;a= (node) malloc( num *

24、 sizeof (status *);printfcn請輸入各路由邊線的cost的權值,如果不存在真接連接請輸 入 10000n，z);for (i=0; ixnum; i+)ai=(status *) malloc( num * sizeof (status);for(j=0;j<num;j+)ai j=maxnum;for (i二0;i<num;i+)for(j=0;j<num;j+)if(i!=j)printf (“請輸入第d個結點到第個%d結點到的權值，i+1, j+1)；scanf (d，&k);/*if( i>二num | j>二num )pr

25、intf (“無效的輸入!請重新輸入！ ！);exit (1);*/ai j二k;elseaij=10000;return a;(2)用node buildl (status num )函數(shù)建立鄰接矩陣用以存放已建立圖的信node buildl (status num )int i, j, k=0;node a;a二(node) malloc( num * sizeof (status *);for (i=0;i<num;i+)ai = (status *) malloc( num * sizeof (status);for(j二0;jnum;j+)aij=maxnum;a00二1000

26、0;a01二2;a02=3;a03二10000;a04二10000 ; a05二10000; a06二10000 ;al 0=2; al 11=10000 ; al 2=4 ; al 3=5 ; al 4=6 ; al5=10000 ; al 61=10000 ;a20二3 ;b21二4 ;a2 2=10000 ;a2 3二 10000 ;a2 41=10000 ;a25二4 ; a6二3 ;a30二 10000 ;a3l二5 ;a3 2二 10000 ;a3 3二 10000 ;a3 41=10000 ;a3 5>10000 ;a3 6=5 ;a40二10000 ;a4l二6 ;a42

27、二10000;a43=10000;a441=10000 ; a45=7; a461=10000;a50=10000 ;a5l=10000 ;a52=4;a53=10000 ;a54=7 ;a55=10000 ;a56=10000 ;a6 0=10000;a6 11=10000;a6 2=3;a.6 3=5;a6 41=10000;a65二 10000; a二4 ;printf 建立路由拓撲：n");for (i=0;i<6;i+)for(j=0;j<6;j+)if(i!=j)if(aij>=10000)printf (，z %d -> %d無直連 ，i+1,

28、j+1);elseprintfc %d】->【d】二二d，i+1, j+l,aij);k+;if(k%4=0)printf(n)；/if/for/forprintf （n）;return a;/cnd4. 結果與結論4.1設計內容dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其 他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展 到終點為止。所以根據(jù)dijkstra算法能得岀最短路徑的最優(yōu)解。最短路徑問題的求解還不止這一種算法，比如還有分枝定界等等，而且大家也 可以創(chuàng)造岀各種各樣的新算法來。不同的最短路徑問題到底用哪種算法，以及還需 要對

29、該種算法作什么改動，是非常重要的，這種能力往往是很多同學所欠缺的，這 需要大家在平常的訓練中多做這類題目，還要多總結，以達到熟能生巧的境界。4.2課程設計程序源程序(1) ” dijkstra. h” 文件程序#ifndef dijkstra_hsdefine d1jkstra_h#includc<stdio. h>#incude<stdlib.h>typedef int status;typedef status * node;/node 扌旨針的指針sdefine maxnum 10000; /設置 10000 為無窮sdefine false 0;#define

30、true 1;/創(chuàng)建結點矩陣void shortestpath dtj( node a , status i ,status vo , status *d , status*pre )/a是傳進的矩陣，i是結點數(shù)，v0是最短路徑的源結點int v, w, j, 1=1;status *final;/設置 int 指針status min;final= (status *)malloc( sizeof(status);/分配空間for (v=0 ;v<i; v+) /初始化finalv=false;prev二false;dv=avo v;if(dv<10000)/找到頭結點prev=

31、vo;for (v=0;v<i;v+)if( avov>=10000 )1+；if(l>i)printf (，zn從路由d出發(fā)沒有最短路徑到其他端點！ n", vo+1); exit (0);)/v0是一個孤立的頂點dv0二0;finalv0二true;for( j=0 ; j<i ; +j )min=maxnum;for ( w=0 ; w<i ; w+)if( ! final w )/判斷是否已被最短路徑路過if ( dw<min )v二 w;min=dw; 找岀最短的路徑finalv=true;for ( w=0 ; w<i ; w+

32、)if( !finalw && ( (min+avw)<dw)dw二min+avw;prew=v;void show (status *d , status *pre , int i , int vo)/d 是最短路徑長度，pre 是最短路徑經(jīng)過的結點，1是結點數(shù)，vo是源結點int j, k, m, n;int *temp;temp=(int *)malloc(sizeof (int)*i);for(j=0;j<i;j+)if(j!二 vo)printf (，zn路由【d】到路由【%d】的最短路徑長度為:%3d” ,vo+1, j+1, dj);n=j;if(dj

33、!=10000)/判斷是不是有可達路徑for(k=0;k<i;k+)tempk=pren;if (temp k !=v0)/判斷是不是源點門身n二tempk;else/(tempk=v0) /是源點跳出break;if( k二二0&&dj!二10000&&dj!二0 )當是源點時printf c路由【%d】->路由%d ", vo+1, j+1);if( k!=0 &&dj!=10000&&dj!=0)/不是源點時for(m=k;m>=0;m-)printf (，z路由【%d】tempm+l);prin

34、tf (z，路由【d】，j+1);if (d j=10000) /沒有路徑printf (，z從路由【d】出發(fā)沒有最短路徑到路±【d】!", vo+1, j+1);if(dj=o)printf c路由【d】，vo);#endif(2) ” floyd. h “文件代碼#ifndef fl0yd_hsdefine fl0yd_httincludc stdio.h>#inelude <stdlib.h>#include <string. h>#define finity 10000/此處用此數(shù)表示無窮大typedef status * node;/

35、node 扌旨針的指針sdcfinc maxnum 10000;/設置 10000 為無窮ftdefine false 0;sdefine true 1;#define m 50/最大頂點數(shù)typedef int distm m;/* 距離向量類型*/typedef int pathm m 40;/* 路徑類型*/*floyd所有頂點對間的最短路徑算法*/void floydl (node g, int num, path &p, dist d)long i, j, k, 1, b;/*初始化*/for (i=0;i<num;i+)for (j=0;j<num;j+)dij

36、二 gij;if (i!=j && dij<finity ) /i 與 j 之間有路徑可通1=0;pi j 1+二i；pi j 1+二j；pi j 1+=t；else pi j 0=-l;for (k=0; k<num; k+)/遞推求解每一對頂點間的最短距離for (i二0; ixnum; i+)for (j=0;j<num;j+)if (dij>dik+dkj)di j二di k+dk j;/刷新距離for (1=0;譏i k 1匸-1; 1+)/譏i k 1匸-1 表示 i, k 間有通路 pijl=pikl;把i, k間的路徑賦給i, j間的路徑

37、for(b=l;pkjb!=l;b+)pi j 1+二pk j b;把 k, j 間的路徑給 i, j 間的路徑 pi j 1二t ；/冊!l新路徑void output_pd(node g, int num, path p, dist d)/*輸出有向圖的最短路徑*/long i, j, 1 ；void putstring(char a);for (i=0;i<num;i+)for(j=0;j<num;j+)printf (，z路由【d】到路由%d的最短路徑不存在,請從新輸入。n, i, j)；break;elseprintf (z，路由【d】與路由【d】z間的最短距離是 dn，

38、i + 1, j+1, di j);printf (，z路由【d】到路由【d】的最短路徑是：路由【d】 ”,i+1, j+l,i+l);for(l=l;pijl!=-l;l+)printfc->路由%d pijl);printf c->路由%d n，j+1);#endif(3) ” main. cppv文件源代碼#include<stdio. h>ttincludc "dijkstrei. h"#inelude "floyd. htypedef int distm m;/* 距離向量類型*/tvpedef int pathm m 40;/*

39、 路徑類型*/typedef status * node;/node 指針的指針ftdefine maxnum 10000;/設置 10000 為無窮sdefine false 0;#define true 1;node build (status num )int i, j, k;node a;a=(node) malloc ( num * sizeof (status *);printf(，zn請輸入各路由邊線的cost的權值，如果不存在真接連接請輸入 10000n);for(i=0;i<num;i+)ai二(status *) malloc( num * sizeof (statu

40、s);for(j=0;j<num;j+)aij=maxnum;for (i=0; ixnum; i+)for(j=0;j<num;j+)if(i!=j)printf ("請輸入第%(1個結點到第個%d結點到的權值"，i+1, j+1); scanf (d，&k);/*if( i>=numj>=num )printf (，z無效的輸入!請重新輸入！ ！);exit 仃)；*/ai j=k;elseaij=10000;return a;node buildl (status num )int i, j, k=0;node a;a= (node)

41、malloc( num * sizcof (status *);for (i=0;i+)ai = (status *) malloc( num * sizeof (status);for(j=0;j<num;j+)aij=maxnum;a0 4=10000 ;a0 0 = 10000;a0l=2; a0 2 =3;a0 3=10000a051=10000;a061=10000 ;al0二2;all二10000 ; al2二4 ; al 3=5；al4=6 ;al51=10000 ;al61=10000 ;a2 0=3;a2 1=4;a2 2=10000;a2 31=10000;a 241

42、=10000 ;a2 5=4 ;a26二3 ;a3 0=10000；a3l=5 ;a32二 10000 ;a3 31=10000 ;a34二 10000 ;a3 51=10000 ; a二5 ;a40二 10000;a4l二 6 ;a42二 10000;a431=10000;a44=10000 ;a45=7; a46=10000;a5 0=10000;a5l=10000;a5 2=4;a5 3=10000 ;a54=7 ;a551=10000 ;a561=10000 ;a60二 10000;a6l二 10000 ;a62二 3 ;a63=5a641=10000;a651=10000;a66二4

43、 ;printf (z，已建立路由拓撲:rt);for (i=0;i<6;i+)for(j=0;j<6;j+)辻(i!=j)if(aij> 二10000)printf (，z %d -> %d無直連 “，i+1, j+1);elseprintf (，z %d -> %d= =%di+1, j+1, ai j);k+;if(k%4 二二 0)printf(n);/if/for/forprintf(n);return a;/endvoid m“in()int i, vo, choice;int w;path p;/*路徑向量*/dist d;/*最短路徑向量*/nod

44、e a;status *d, *pre;while (1)*、n")； printf (n printf (“ printf (“ printf (“startl:請選擇:n）；1. 自己制作路曲拓補圖nnz，）;2. 使用已做好的路由拓補圖nrt）;printf ("3. 退出！ nn）;>lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >

45、lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz >lz lz*nri)；printf（，z請輸入你的選擇：“）;scanf（d，&a

46、mp;choice）;if (choice二二3)break;else if(choice>3 choice<0 choice%l!=0)ptintf ("error!請重新選擇n");goto startl;switch(choice)case 1:start:printf (請輸入網(wǎng)絡拓補中路由器總數(shù):)；scanf(%d, &i );if(i<=0| i%l !二0)printfc你輸入的路由器的個數(shù)有誤，請重新輸入)；goto steirt;/printf ("input the arcs:/z);/scanf (ct,&

47、j);的結點d= (status *)malloc(sizeof (status)*i) ;/用于存放最短路徑長度 pre= (status *)malloc(sizeof (status)*i) ;/用于存放最短路徑經(jīng)過a二bu訂d(i);/printf(，zplease input the start node: ”)；/scanf(d，&v0);aif(vo>i)printf("input errors!not excite this node!)；exit 仃)；*/break;case 2:i 二7;a=buildl (7);d二(status *)mallo

48、c(sizeof (status)*i) ;/用 j：存放最短路徑長度 prc= (status *)malloc(sizeof (status)*i) ;/用于存放最短路徑經(jīng)過 的結點/* printf (，zplease in put the start node: “)；scanf (ct, &v0);if(v0>8)printf("input errors!not excite this node!)；exit (1);*/break;/w itchprintf (“l(fā)oop:彳.xt'x xt'x xt'x xt'x xt

49、9;x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x

50、 xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x xt'x*、n")；printf ("printf (“printf (“請選擇算法：nn)；1選用 di jkstra. h 算法。nn，z);printf (“2.選用 floyd 算法。nn，z);viz

51、 viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz viz*n)；printf r 請選擇:)；seanf(d，&choice);if (choice!二1&&c

52、hoice!二2)printf ("error, please input againn，z);goto loop;switch(choice)case 1:for (vo二1;vo<=i;v0+)shortestpath_dlj ( a , i ,vol ,d , pre );show( d, pre, i, vol );break;case 2:floydl (a, i, p, d);output_pd (a, i, p, d);break;printfcnn你是否還想再嘗試一次?是請輸入1,不想請輸入0結束! 請選擇：)；scanf("%d，&w);if

53、(w!=l)break;/while4.3程序輸出圖4.3.1程序主界面丄4 丄"丄"丄"丄"丄"4丄"丄"丄"丄 丄"丄"丄 丄"丄"丄"丄"丄"丄 丄"丄"丄"丄"丄"丄"丄"丄"丄 丄"丄丄丄 丄"丄"丄"4丄 丄"丄"丄"丄"丄"丄"丄"丄"丄"丄"丄"丄"丄 丄"丄"丄"丄"丄"丄"7 丫、，丫、刁丫、，丫、，丫、刁丫、刁丫、，丫、刁丫、，丫、刁丫、，丫、e*t 刁丫、刁丫、刁丫、，丫、