用C語言編程實(shí)現(xiàn)最短路徑道客巴巴

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

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

2、ge Xinjinrong (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.Me

3、t the most short?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 intersecti

4、on distance, how 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, progr

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

6、一一即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。 最短路徑問題研究的問題主要有：?jiǎn)卧醋疃搪窂絾栴}、與所有頂點(diǎn)對(duì)之間的最短路徑問 題。 1. 1最短路徑的基本概念 1. 2與其相關(guān)的概念 為了更好理解什么是最短路徑，首先我們就該清楚以下的問題。 (1) 通路：在一序列中，中間每個(gè)結(jié)點(diǎn)均與其前、后結(jié)點(diǎn)相鄰接，這種邊的序列稱為 圖的通路。通路中邊的數(shù)目稱為通路的長(zhǎng)度。 (2) 回路：圖中一條通路如果起始結(jié)點(diǎn)與終止結(jié)點(diǎn)相同，則稱此通路為回路。 (3) 簡(jiǎn)單路徑：有向圖中各邊全不同的通路稱為簡(jiǎn)單路徑。 (4) 基本路徑：有向圖中各點(diǎn)全不同的通路稱為基本路徑。 2最短路徑的意義及其在現(xiàn)實(shí)生產(chǎn)

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

8、 些概念體系稱為模型。把邏輯應(yīng)用與模型的概念而得到的見解稱為理論。數(shù)學(xué)模型是各種模 型中最嚴(yán)密的模型。其正確性是通過邏輯和實(shí)踐來檢驗(yàn)。20世紀(jì)數(shù)學(xué)模型有了很大的發(fā)展。 其原因有三：一，數(shù)學(xué)理論的系統(tǒng)化，二，計(jì)算機(jī)的誕生，三，應(yīng)用數(shù)學(xué)的大發(fā)展。 數(shù)學(xué)就是一個(gè)對(duì)未來作出預(yù)見的重要工具，它常常能以足夠的精確度對(duì)未來作出預(yù)見, 告訴我們未來的發(fā)展趨勢(shì)。數(shù)學(xué)模型就像一張指示方向的交通圖，也像建筑的設(shè)計(jì)圖，雖然 簡(jiǎn)單卻切中要害。 數(shù)學(xué)模型在各方面影響著我們。從大的方面講，財(cái)政預(yù)算，人口控制；從個(gè)人角度講, 以購房為例，除去交預(yù)付款外，還要每刀扣除。這都需要數(shù)學(xué)模型的幫助。 數(shù)學(xué)模型可以分為連續(xù)型模型

9、、離散型模型、隨機(jī)型模型等。數(shù)學(xué)模型建立一般分為五 個(gè)階段： (1) 科學(xué)地識(shí)別與剖析實(shí)際問題； (2) 形成數(shù)學(xué)模型； (3) 求解數(shù)學(xué)問題； (4) 研究算法，并盡量使用計(jì)算機(jī)； (5) 回到實(shí)際中去，解釋結(jié)果。 最短路徑的實(shí)現(xiàn)必須借助圖、矩陣等數(shù)學(xué)工具。 3. 2具體實(shí)現(xiàn)舉例 己知某人有一張A城市的內(nèi)部交通圖，公交車從第一站出發(fā)可以到第二站、第三站及 第四站，它們的費(fèi)用分別是6元、3元和1元；從第二站可以到第五站，費(fèi)用為1元；從 第三站可以到第二站和第四站，費(fèi)用都為2元；從第四站可以到第六站，費(fèi)用為10元；從 第五站可以到第六站、第七站及第八站，費(fèi)用分別為4元、3元和6元

10、；從第六站可以到 第五站和第七站，費(fèi)用分別為10元和2元；從第七站可以到第九站，費(fèi)用為4元從第八站 可以到第五站和第九站，費(fèi)用分別為2元和3元；某人想從第一站到第八站去，求使總費(fèi) 用最小的旅行路線。 3. 2.1實(shí)例轉(zhuǎn)換為有向圖 下圖為上述文字轉(zhuǎn)換的有向加權(quán)圖G= (V, E,W)，其屮V為頂點(diǎn)集，Vn表示每一站，有 多少站就有多少個(gè)結(jié)點(diǎn)，n可以取1, 2, 3,……，n； E為有向邊集，有邊表示兩站之間是 相通的；W為邊上的權(quán)集，邊上標(biāo)注的數(shù)字表示邊的大小，邊的大小表示費(fèi)用；箭頭指向的 結(jié)點(diǎn)為終止結(jié)點(diǎn)，沒有箭頭的邊表示這兩站之間相互通車，費(fèi)用相同。 鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩

11、陣，設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，則G的領(lǐng) v8 3 v9 接矩陣是具有如下性質(zhì)的n階方陣: A= (ajj) nXn 其中 ajj=O,若從Vj到vj無邊相連； ajj=w,若從Vj到Vj有邊相連且此邊的權(quán)為w； 矩陣的列表示的是起始結(jié)點(diǎn)；行表示的是終止結(jié)點(diǎn)；兩結(jié)點(diǎn)間如果相通，數(shù)字表示兩結(jié) 點(diǎn)間邊的大小，如果不相通，就沒有邊的大小，用“0”農(nóng)示。 0 2 0 2 0 0 0 0 A= 0 0 0 6 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 4 3

12、 0 6 10 0 2 0 0 0 0 0 0 4 2 0 0 0 3 0 0 0 0 0 3. 2. 3矩陣的運(yùn)算及其意義 表示兩結(jié)點(diǎn)之間長(zhǎng)度為n的通路，這里的長(zhǎng)度是指兩結(jié)點(diǎn)之間邊的數(shù)目。所以我們 要計(jì)算出An (n的取值為結(jié)點(diǎn)的個(gè)數(shù))。 _0 6 3 1 0 0 0 0 0_ _0 6 3 1 0 0 0 0 — 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 2 0 0 0 0 0 0 2

13、 0 2 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 6 0 4 3 0 6 X 0 0 0 6 0 4 3 0 6 0 0 0 0 10 0 2 0 0 0 0 0 0 10 0 2 0 0 () 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 2 0 0 0 3 0 0 0 0 2 0

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

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

16、d(vlz vl)+wl3 = 3單位的費(fèi)用；類似地，若沿(vl, v4)到達(dá)v4,這時(shí)需 要 d(vlz vl)+wl4=l 單位的費(fèi)用。因?yàn)?min{ d(vlz vl)+wl2,d(vlz vl)+wl3,d(vlz vl)+wl4}= d(vl, vl)+wl4=l,可以斷言，他從vl到v4所需要的最小費(fèi)用必定是1 單位，即從vl到v4的最短路是(vl, v4), d(vlz v4) = lo這是因?yàn)閺膙l到v4的任一 條路P,如果不是(vlzv4),則必是先從vl沿(vl,v2)到達(dá)v2,或者沿(vl,v3)到達(dá)v3。 但如上所說，這吋他已需要6單位或3單位的費(fèi)用，不管他如何再從v2

17、或從v3到達(dá)V4, 所需要的總費(fèi)用都不會(huì)比1小(因?yàn)樗衱ij>0)o W而推知d(vl, v4) = l,這樣就可以使 v4變成具P標(biāo)號(hào)的點(diǎn)?，F(xiàn)在考察從vl及v4指向其余點(diǎn)的弧，由上已知，從vl岀發(fā)，分別沿(vl, v2). (vlzv3)到達(dá)v2, v3,需要的費(fèi)用分別為6與3,而從v4出發(fā)沿(v4, v6) 到達(dá) v6 所需的費(fèi)用是 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的最短路是(vl,

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

19、= O 對(duì)每一個(gè) voVs,令 T(v) = +8, A(v) = + oo, k=s ｛開始｝ ① 如果Si=V,算法終止,這時(shí),每個(gè)veSi, d(Vszv)=P(v)；否則轉(zhuǎn)入② ② 考察每個(gè)使(Vk,vj)eE且vj Si的點(diǎn)vj0 如果 T(vj)>P(vk)+wkj,則把 T(vj)修改為 P(vk)+wkj,把入(vj)修改為 k。 ) < +8 ③ 令 500){this.resized=true;this.style.width = 500;}H align=middle> 500){this. resized=true;this.style.width =

20、500;}" align = middle> ,貝9 把 500){this?resized=tTue;this?sHc 宀一匚 align=middle> 的 標(biāo) 號(hào) 變 為 P 標(biāo) 號(hào) 卩"叫)—"叫) 匚am“心 ^^ed=true;this.style.width = 500;}H align = middle> , 令 Sixl = Si u (v,.) 1 幾 500){this. resized=true;this.style.width = 500;}" align = middle> , k=ii, i=i+l,轉(zhuǎn)①，否則終止,這時(shí)對(duì)每一個(gè) veSi, d(vs,

21、v) = P(v), 而對(duì)每一個(gè)$"(匕v) - T(y) 500){this.resized=true;this.style.width = 500;}" align = middle＞。 4.1. 2算法的描敘過程 Program Min Road Dijkstra; Const MaxN=100; Type GraphType=Array[1?? MaxN, 1?? MaxN, ]of integer; 有向圖鄰接矩陣} Var w : GraphType; ｛圖G結(jié)構(gòu)，W[I, j]表示頂點(diǎn)i到j(luò)之間的費(fèi)用｝ s, n, : integer; ｛s為源點(diǎn)，n為圖G的頂點(diǎn)

22、數(shù)｝ ｛存放從源點(diǎn)到任意頂點(diǎn)之間的最短路徑長(zhǎng)度或其上界｝ D : array[1?? MaxN] of integer; SS : array[1.. MaxN] of boolean; ｛標(biāo)有 P 標(biāo)號(hào)的頂點(diǎn)集合｝ ｛p[i]存放最短路中頂點(diǎn)i的前面頂點(diǎn)編號(hào)｝ p : array[1.. MaxN] of integer; Procedure Init; ｛｝ Var f :text; x, y, nw, I, j: integer; begin assign(f, miniroad\road? in); reset(f); readln(f, n, s, nw);

23、 for i:=1 to n do for j:= 1 to n do 500) ｛this?resized二true;this, style. width=500;｝ "resized二true" > w[i,j]:=Maxinit; for i:=1 to nw do readln(f, x, y, w[x, y]); close(f); end; Procedure Di jkstra; ｛ Di jkstra 算法過程｝ var min, k, i, j, tempk:integer; begin fillchar(SS, sizeof(SS), 0); ｛*

24、******* 初始化******** j SS[s] :=true;p[s] :=0; ｛源點(diǎn)標(biāo)上 p 標(biāo)號(hào)｝ for i:=1 to n do if iOs then D[i]:二w[s, i]; D[s]:=0; k:=s; min:二T; While minOMaxint do ｛當(dāng)存在所有T標(biāo)號(hào)點(diǎn)的距離上界的最小值｝ Begin min:= Maxint; for j:=l to n do begin ｛在所有T標(biāo)號(hào)點(diǎn)進(jìn)行操作｝ 500) ｛this # resizcd=true;this? stylc. width=500;｝ > ｛如果j未標(biāo)p標(biāo)號(hào)，且到j(luò)

25、的路徑長(zhǎng)度上界可更新，則更新為最小值｝ if (not ss[j])and(w[k, j]OMaxint)and(d[j]>D[k]+w[k, j]) then begin D[j]:= D[k]+w[k, j]; D[j]:二k; end; end; if n)in< Maxi nt then begin ｛如果找到,則該點(diǎn)標(biāo)上p標(biāo)號(hào)｝ k:二temp; ss[k]:=true; end; end; end; Procedure Print; ｛打印出路徑｝ var I,j:integer; temps,temppath:string; begin 500)

26、｛this?resized=true;this .style?width二500;｝ “resized二true” > 4. 2算法對(duì)應(yīng)的源程序 # i nclude # i nelude //Di jkstra算法實(shí)現(xiàn)函數(shù) void Dijkstradnt n, int v, int dist[], int prev[], int **cost) ｛ int i; int j； int maxint二65535;//定義一個(gè)最大的數(shù)值，作為不相連的兩個(gè)節(jié)點(diǎn)的代價(jià)權(quán)值 int *s ;//定義具有最短路徑的節(jié)點(diǎn)子集s s = (i

27、nt *)malloc(sizeof(int) * n); //初始化最小路徑代價(jià)和前一跳節(jié)點(diǎn)值 for (i = 1; i <= n; i卄) { dist [i] = cost[v] [i]; s[i] = 0; if (dist[i] == maxint) { prev[i] = 0; } else { prev[i] = v; } } dist[v] = 0; s[v] = 1;//源節(jié)點(diǎn)作為最初的s子集 for (i = 1; i < n; i卄) f int temp = maxint; int u = v; 〃加入具有最小代價(jià)的鄰居節(jié)點(diǎn)到

28、s 了集 for (j = 1; j 〈二 n; j++) { if ((!s[j]) && (dist[j] < temp)) { u = j; temp = dist[j]; } } s[u] = 1; 〃計(jì)算加入新的節(jié)點(diǎn)后，更新路徑使得其產(chǎn)生代價(jià)最短 for (j = 1; j 〈二 n; j++) if ((!s[jj) && (cost[u][j] < maxint)) int newdist = dist[u] + cost[u][j]; if (newdist < dist[j]) dist [j] = newdist; prev[j] = u; }

29、} } } } //展示最佳路徑函數(shù) void ShowPath(int n, int v,int u, int *dist, int *prev) { int j = 0; int w = u; int count = 0; int *way ; way=(int *)malloc(sizeof(int)*(n+1)); 〃回溯路徑 while (w != v) { count++; way[count] = prev[w]; w = prev[w]; } //輸出路徑 printf("the best path is:\n〃)； for (j =

30、count; j >= 1; j--) { printf (，z%d -> ", way[j]); } printf (〃％d\n", u); } //主函數(shù)，主要做輸入輸出工作 void main() int i, j, t; int n, v, u; int **cost;〃代價(jià)矩陣 int *dist;//最短路徑代價(jià) int *prev;//前一跳節(jié)點(diǎn)空間 printf("please input the node number:"); scanf&n); printf(^please input the cost status:\n"); cost=(

31、int. **)malloc(sizeof (int)*(n+1)); for (i = 1; i <= n; i++) { cost[i] = (int *)malloc(sizeof(int)*(n+1)); } //輸入代價(jià)矩陣 for (j = 1; j <= n; j++) { for (t = 1; t 〈二 n; t++) { scanf&cost[j] [t]); } } dist = (int *)malloc(sizcof(int)*n); prev = (int *)malloc(sizeof(int)*n); printf("please i

32、nput the source node:"); scanf&v); //調(diào)用di jkstra算法 Di jkstra(n, v, dist, prev, cost); printf (have confirm the best path\n"); printf("*****************************\n"); for(i = 1; i <= n ; i++) if(i!=v) { printf (z，the distance cost from node %d to node %d is %d\n/z, v, i, dist[i]); print

33、f (z，the pre-node of node %d is node %d \n \ i, prcv[i]); ShowPath(n, v, i, dist, prev); } } } ////////////////// 程序運(yùn)行結(jié)果: cT *D:\orkSpace\dj6\Debug\djBe.exe* please input the node number： 6 please input the cost status: 0251 65535 65535 2032 65535 65535 5 3 0 3 1 5 12301 65535 65535 65535

34、 1102 65535 65535 5 65535 2 0 please input the source node: 2 have conf irn the best path the distance cost fron node 2 to node 1 is 2 the pre-node of node 1 is node 2 the best path is: 2 -： 1 the distance cost fron node 2 to node 3 is 3 the pre

35、-node of node 3 is node 2 the best path is: 2 -： > 3 the distance cost fvon node 2 to node 4 is 2 the pi*e-node of node 4 is node 2 the best path is: 2 > 4 the distance cost fron node 2 to node 5 is 3 the pre-node of

36、 node 5 is node 4 the best path is: 2 -： > 4 -> 5 the distance cost from node 2 to node 6 is 5 the pre-node of node 6 is node 5 the best path is: 2 -> 4 -> 5 -> 6 Pfgss any key to continue 5結(jié)束語 參考文獻(xiàn) [1]徐潔磐.離散數(shù)學(xué)導(dǎo)論一3版.北京:髙等教育岀版社,2004.6 ［2］謝永欽?試論信息與計(jì)算機(jī)科學(xué)專業(yè)的改革與發(fā)展［J］?數(shù)學(xué)理論與應(yīng)用，2002,22(4):45)6 ⑶同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系.丁程數(shù)學(xué)線性代數(shù).北京:高等教育出版社.http://www.hep.edu.en/.2003.7 ［4］隴東學(xué)院教務(wù)處?教學(xué)計(jì)劃［ZJ.200L12