《用C語言編程實現(xiàn)最短路徑道客巴巴》由會員分享，可在線閱讀，更多相關(guān)《用C語言編程實現(xiàn)最短路徑道客巴巴（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、用C語言編程實現(xiàn)最短路徑摘 要：最短路徑問題研究的問題主要有：單源最短路徑問題、與所有頂點對之間 的最短路徑問題。在我們的生產(chǎn)生活中遇到最短路徑的問題實在太多了，比如乘汽車旅 行的人總希望找出到目的地盡可能的短的行程。如果有一張地圖并在圖上標(biāo)出每對十字 路口之間的距離，如何找出這一最短行程？我們首先應(yīng)該建立它的數(shù)學(xué)模型，借助圖、 矩陣等數(shù)學(xué)工具，然后根據(jù)數(shù)學(xué)模型寫出的算法及其源程序。關(guān)鍵詞：C語言，編程，最短路徑中圖分類號：G343Programs the realization most short-path wages hibiscuswith the C languageXinjinro

2、ng(east Gansu institute computer and the information science institute 2007 level of 4 class of Gansu Qingyang 745000)the abstract: The most short-path question research question mainly has: Simple source most short-path question, and all apexes to between most short-path question.Met the most short

3、palh in ours production life the question too to be really many, for instance rode the automobile travel the human always hoped discovered to destination as far as possible short traveling schedule.If has a map and leaves in the chart superscript every time to between the intersection distance, how

4、discovers this shortest traveling schedule? We first should establish its mathematical model, with the aid of mathematical instruments and so on the chart, matrix, then the algorithm and the source program which writesaccording to the mathematical model.Key word: C language, programming, most shortp

5、alh Chinese Libraryclassification number: G3431最短路徑及其相關(guān)概念最短路徑問題是圖論研究中的-個經(jīng)典算法問題，旨在尋找圖(由結(jié)點和路徑組成的) 中兩節(jié)點之間的最短路徑。算法具體的形式包括：(1) 確定起點的最短路徑問題一一即已知起始結(jié)點，求最短路徑問題。(2) 確定終點的最短路徑問題一一與確定起點的問題相反，該問題是已知終結(jié)結(jié)點， 求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，再有向圖中該問題等同 于把所有路徑方向反轉(zhuǎn)的確定起點的問題。(3) 確定起點終點的最短路徑問題一一即已知起點和終點，求兩結(jié)點之間的最短路徑。 最短路徑問題研究

6、的問題主要有：單源最短路徑問題、與所有頂點對之間的最短路徑問 題。1. 1最短路徑的基本概念1. 2與其相關(guān)的概念為了更好理解什么是最短路徑，首先我們就該清楚以下的問題。(1) 通路：在一序列中，中間每個結(jié)點均與其前、后結(jié)點相鄰接，這種邊的序列稱為 圖的通路。通路中邊的數(shù)目稱為通路的長度。(2) 回路：圖中一條通路如果起始結(jié)點與終止結(jié)點相同，則稱此通路為回路。(3) 簡單路徑：有向圖中各邊全不同的通路稱為簡單路徑。(4) 基本路徑：有向圖中各點全不同的通路稱為基本路徑。2最短路徑的意義及其在現(xiàn)實生產(chǎn)生活中的應(yīng)用在我們的生產(chǎn)生活中遇到最短路徑的問題實在太多了，比如乘汽車旅行的人總希望找出 到目的

7、地盡可能的短的行程。如果有一張地圖并在圖上標(biāo)岀每對十字路口之間的距離，如何 找岀這一最短行程？種可能的方法就是枚舉岀所有路徑，并計算出每條路徑的長度，然后選擇最短的條。 我們很容易看到，即使不考慮包含回路的路徑，依然存在數(shù)以萬計的行千路線，而其屮絕大 多數(shù)是不值得考慮的。我們將闡明如何有效地解決這類問題。在最短路徑問題中，我們?nèi)绾螌⑽淖謹(jǐn)⑹鲛D(zhuǎn)換為 數(shù)學(xué)模型呢？3最短路徑的數(shù)學(xué)模型實現(xiàn)3.1數(shù)學(xué)模型數(shù)學(xué)模型是人們?yōu)榱肆私庵茑龅氖澜?，把口己的觀察及思想組織成概念體系。我們把這 些概念體系稱為模型。把邏輯應(yīng)用與模型的概念而得到的見解稱為理論。數(shù)學(xué)模型是各種模 型中最嚴(yán)密的模型。其正確性是通過邏輯和實

8、踐來檢驗。20世紀(jì)數(shù)學(xué)模型有了很大的發(fā)展。 其原因有三：一，數(shù)學(xué)理論的系統(tǒng)化，二，計算機的誕生，三，應(yīng)用數(shù)學(xué)的大發(fā)展。數(shù)學(xué)就是一個對未來作出預(yù)見的重要工具，它常常能以足夠的精確度對未來作出預(yù)見, 告訴我們未來的發(fā)展趨勢。數(shù)學(xué)模型就像一張指示方向的交通圖，也像建筑的設(shè)計圖，雖然 簡單卻切中要害。數(shù)學(xué)模型在各方面影響著我們。從大的方面講，財政預(yù)算，人口控制；從個人角度講, 以購房為例，除去交預(yù)付款外，還要每刀扣除。這都需要數(shù)學(xué)模型的幫助。數(shù)學(xué)模型可以分為連續(xù)型模型、離散型模型、隨機型模型等。數(shù)學(xué)模型建立一般分為五 個階段：(1) 科學(xué)地識別與剖析實際問題；(2) 形成數(shù)學(xué)模型；(3) 求解數(shù)學(xué)問題

9、；(4) 研究算法，并盡量使用計算機；(5) 回到實際中去，解釋結(jié)果。最短路徑的實現(xiàn)必須借助圖、矩陣等數(shù)學(xué)工具。3. 2具體實現(xiàn)舉例己知某人有一張A城市的內(nèi)部交通圖，公交車從第一站出發(fā)可以到第二站、第三站及 第四站，它們的費用分別是6元、3元和1元；從第二站可以到第五站，費用為1元；從 第三站可以到第二站和第四站，費用都為2元；從第四站可以到第六站，費用為10元；從 第五站可以到第六站、第七站及第八站，費用分別為4元、3元和6元；從第六站可以到 第五站和第七站，費用分別為10元和2元；從第七站可以到第九站，費用為4元從第八站 可以到第五站和第九站，費用分別為2元和3元；某人想從第一站到第八站去

10、，求使總費 用最小的旅行路線。3. 2.1實例轉(zhuǎn)換為有向圖下圖為上述文字轉(zhuǎn)換的有向加權(quán)圖G= (V, E,W)，其屮V為頂點集，Vn表示每一站，有 多少站就有多少個結(jié)點，n可以取1, 2, 3,，n； E為有向邊集，有邊表示兩站之間是 相通的；W為邊上的權(quán)集，邊上標(biāo)注的數(shù)字表示邊的大小，邊的大小表示費用；箭頭指向的 結(jié)點為終止結(jié)點，沒有箭頭的邊表示這兩站之間相互通車，費用相同。鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣，設(shè)G=(V,E)是具有n個頂點的圖，則G的領(lǐng)v83v9接矩陣是具有如下性質(zhì)的n階方陣:A= (ajj) nXn其中ajj=O,若從Vj到vj無邊相連；ajj=w,若從Vj到Vj有邊相

11、連且此邊的權(quán)為w；矩陣的列表示的是起始結(jié)點；行表示的是終止結(jié)點；兩結(jié)點間如果相通，數(shù)字表示兩結(jié)點間邊的大小，如果不相通，就沒有邊的大小，用“0”農(nóng)示。0 2 0 20 0 0 0A= 0 0 0 60 0 0 0000001000000000010000043061002000000420003000003. 2. 3矩陣的運算及其意義表示兩結(jié)點之間長度為n的通路，這里的長度是指兩結(jié)點之間邊的數(shù)目。所以我們 要計算出An (n的取值為結(jié)點的個數(shù))。_063100000_063100000000010000000010000020200000020200000000001000000000100

12、00000604306X00060430600001002000000100200()00000004000000004000020003000020003000000000_000000000_在求出A*1后我們就可求出可達性矩陣，Rn=A+A2+A3+.+An一個圖G的可達性矩陣給出了圖中各結(jié)點間是否可達以及圖中是否有回路。4 c語言編程實現(xiàn)4. 1算法的基本思想(數(shù)組實現(xiàn))4.1.1基本思想Dijkstra算法的基本思想是從從vs出發(fā)，逐步地向外探尋最短路。執(zhí)行過程中，與每 個點對應(yīng)，記錄下一個數(shù)(稱為這個點的標(biāo)號)，它或者表示從vs到該點的最短路的權(quán)(稱為 P標(biāo)號)、或者是從VS到該點

13、的最短路的權(quán)的上界(稱為T標(biāo)號)，方法的每一步是去修改T 標(biāo)號，并且把某一個具T標(biāo)號的改變?yōu)榫逷標(biāo)號的點，從而使G中具P標(biāo)號的頂點數(shù)多一 個，這樣至多經(jīng)過nl(n為圖G的頂點數(shù))步，就可以求出從vs到各點的最短路。在敘述Dijkstra方法的具體步驟之前，以例1為例說明一下這個方法的基本思想。例 1中，s=lo因為所有Wij0,故有d(vlz vl)=Oo這時，vl是具P標(biāo)號的點?，F(xiàn)在考 察從vl發(fā)出的三條弧,(vl, v2)z (vlz v3)和(vl, v4)。如果某人從vl出發(fā)沿(vl, v2) 到達v2,這時需要d(vlz vl)+wl2=6單位的費用；如果他從vl出發(fā)沿(vl, v3

14、)到達 v3,這時需要d(vlz vl)+wl3 = 3單位的費用；類似地，若沿(vl, v4)到達v4,這時需 要 d(vlz vl)+wl4=l 單位的費用。因為 min d(vlz vl)+wl2,d(vlz vl)+wl3,d(vlz vl)+wl4= d(vl, vl)+wl4=l,可以斷言，他從vl到v4所需要的最小費用必定是1 單位，即從vl到v4的最短路是(vl, v4), d(vlz v4) = lo這是因為從vl到v4的任一 條路P,如果不是(vlzv4),則必是先從vl沿(vl,v2)到達v2,或者沿(vl,v3)到達v3。 但如上所說，這吋他已需要6單位或3單位的費用，

15、不管他如何再從v2或從v3到達V4, 所需要的總費用都不會比1小(因為所有wij0)o W而推知d(vl, v4) = l,這樣就可以使 v4變成具P標(biāo)號的點?，F(xiàn)在考察從vl及v4指向其余點的弧，由上已知，從vl岀發(fā)，分別沿(vl, v2). (vlzv3)到達v2, v3,需要的費用分別為6與3,而從v4出發(fā)沿(v4, v6) 到達 v6 所需的費用是 d(vlz v4)+w46=l + 10=ll 單位。因 min d(vlz vl)+wl2, d(vl, vl)+wl3, d(vl, v4)+w46= d(vlz vl)+wl3 = 3o 基于同樣的理由可以斷言, 從vl到v3的最短路是

16、(vl, v3), d(vl, v3) = 3o這樣又可以使點v3變成具P標(biāo)號的點, 如此重復(fù)這個過程，可以求出從vl到任一點的最短路。在下述的Dijstra方法具體步驟中，用P, T分別表示某個點的P標(biāo)號、T標(biāo)號，si表示第i步時，具P標(biāo)號點的集合。為了在求岀從vs到各點的距離的同時，也求岀從Vs到 各點的最短路，給每個點v以一個入值，算法終止時A(v) = m,表示在Vs到v的最短路上，v的前一個點是Vm；如果入(v) = 8,表示圖G中不含從Vs到v的路；入(Vs) = O。Dijstra方法的具體步驟：初始化i=0SO=Vs, P(Vs) = O A(Vs) = O對每一個 voVs,

17、令 T(v) = +8, A(v) = + oo, k=s開始 如果Si=V,算法終止,這時,每個veSi, d(Vszv)=P(v)；否則轉(zhuǎn)入 考察每個使(Vk,vj)eE且vj Si的點vj0如果 T(vj)P(vk)+wkj,則把 T(vj)修改為 P(vk)+wkj,把入(vj)修改為 k。) 500)this. resized=true;this.style.width = 500;align = middle ,貝9 把 500)thisresized=tTue;thissHc 宀一匚 align=middle 的 標(biāo) 號 變 為 P 標(biāo) 號 卩叫)叫)匚am“心 ed=true;

18、this.style.width = 500;Halign = middle , 令Sixl = Si u (v,.)1幾500)this. resized=true;this.style.width = 500;align = middle , k=ii, i=i+l,轉(zhuǎn)，否則終止,這時對每一個 veSi, d(vs,v) = P(v), 而對每一個$(匕v) - T(y) 500)this.resized=true;this.style.width = 500; align = middle。4.1. 2算法的描敘過程Program Min Road Dijkstra;Const MaxN

19、=100;Type GraphType=Array1 MaxN, 1 MaxN, of integer;有向圖鄰接矩陣Varw :GraphType; 圖G結(jié)構(gòu)，WI, j表示頂點i到j(luò)之間的費用s, n, :integer; s為源點，n為圖G的頂點數(shù)存放從源點到任意頂點之間的最短路徑長度或其上界D:array1MaxNofinteger;SS:array1.MaxNofboolean;標(biāo)有 P標(biāo)號的頂點集合pi存放最短路中頂點i的前面頂點編號p:array1.MaxNofinteger;Procedure Init;Var f :text;x, y, nw, I, j: integer;b

20、eginassign(f, miniroadroad in);reset(f);readln(f, n, s, nw);for i:=1 to n dofor j:= 1 to n do500) thisresized二true;this, style.width=500; resized二true wi,j:=Maxinit;for i:=1 to nw doreadln(f, x, y, wx, y);close(f);end;Procedure Di jkstra; Di jkstra 算法過程var min, k, i, j, tempk:integer;beginfillchar(S

21、S, sizeof(SS), 0);* 初始化* jSSs :=true;ps :=0; 源點標(biāo)上 p 標(biāo)號for i:=1 to n doif iOs then Di:二ws, i;Ds:=0;k:=s;min:二T;While minOMaxint do 當(dāng)存在所有T標(biāo)號點的距離上界的最小值Beginmin:= Maxint;for j:=l to n do begin 在所有T標(biāo)號點進行操作500) this# resizcd=true;this stylc. width=500; 如果j未標(biāo)p標(biāo)號，且到j(luò)的路徑長度上界可更新，則更新為最小值if (not ssj)and(wk, jOM

22、axint)and(djDk+wk, j) then beginDj:= Dk+wk, j;Dj:二k;end;end;if n)in4. 2算法對應(yīng)的源程序# i nclude# i nelude /Di jkstra算法實現(xiàn)函數(shù)void Dijkstradnt n, int v, int dist, int prev, int *cost)int i;int j；int maxint二65535;/定義一個最大的數(shù)值，作為不相連的兩個節(jié)點的代價權(quán)值int *s ;/定義具有最短路徑的節(jié)點子集ss = (int *)malloc(sizeof(int) * n);/初始化最小路徑代價和前一跳

23、節(jié)點值for (i = 1; i = n; i卄)dist i = costv i;si = 0;if (disti = maxint)previ = 0;elseprevi = v;distv = 0;sv = 1;/源節(jié)點作為最初的s子集for (i = 1; i n; i卄)fint temp = maxint;int u = v;加入具有最小代價的鄰居節(jié)點到s 了集for (j = 1; j 二 n; j+)if (!sj) & (distj temp)u = j;temp = distj;su = 1;計算加入新的節(jié)點后，更新路徑使得其產(chǎn)生代價最短 for (j = 1; j 二 n

24、; j+)if (!sjj) & (costuj maxint) int newdist = distu + costuj; if (newdist = 1; j-)printf (，z%d - , wayj);printf (dn, u);/主函數(shù)，主要做輸入輸出工作void main()int i, j, t;int n, v, u;int *cost;代價矩陣int *dist;/最短路徑代價int *prev;/前一跳節(jié)點空間printf(please input the node number:);scanf&n);printf(please input the cost statu

25、s:n);cost=(int. *)malloc(sizeof (int)*(n+1);for (i = 1; i = n; i+)costi = (int *)malloc(sizeof(int)*(n+1);/輸入代價矩陣for (j = 1; j = n; j+)for (t = 1; t 二 n; t+)scanf&costj t);dist = (int *)malloc(sizcof(int)*n);prev = (int *)malloc(sizeof(int)*n); printf(please input the source node:);scanf&v);/調(diào)用di jk

26、stra算法Di jkstra(n, v, dist, prev, cost);printf (have confirm the best pathn);printf(*n); for(i = 1; i 3thedistance cost fvon node 2tonode4is2thepi*e-node of node 4 is node2thebest path is:2 4thedistance cost fron node 2tonode5is3thepre-node of node 5 is node4thebest path is:2 -： 4 - 5thedistance cost from node 2tonode6is5thepre-node of node 6 is node5the best path is:2 - 4 - 5 - 6Pfgss any key to continue5結(jié)束語參考文獻1徐潔磐.離散數(shù)學(xué)導(dǎo)論一3版.北京:髙等教育岀版社,2004.62謝永欽試論信息與計算機科學(xué)專業(yè)的改革與發(fā)展J數(shù)學(xué)理論與應(yīng)用，2002,22(4):45)6同濟大學(xué)應(yīng)用數(shù)學(xué)系.丁程數(shù)學(xué)線性代數(shù).北京:高等教育出版社.http:/www.hep.edu.en/.2003.74隴東學(xué)院教務(wù)處教學(xué)計劃ZJ.200L12