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

1、用C語言編程實現(xiàn)最短路徑 摘 要：最短路徑問題研究的問題主要有：單源最短路徑問題、與所有頂點對之間 的最短路徑問題。在我們的生產(chǎn)生活中遇到最短路徑的問題實在太多了，比如乘汽車旅 行的人總希望找出到目的地盡可能的短的行程。如果有一張地圖并在圖上標出每對十字 路口之間的距離，如何找出這一最短行程？我們首先應(yīng)該建立它的數(shù)學(xué)模型，借助圖、 矩陣等數(shù)學(xué)工具，然后根據(jù)數(shù)學(xué)模型寫出的算法及其源程序。 關(guān)鍵詞：C語言，編程，最短路徑 中圖分類號：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)概念 最短路徑問題是圖論研究中的-個經(jīng)典算法問題，旨在尋找圖(由結(jié)點和路徑組成的) 中兩節(jié)點之間的最短路徑。算法具體的形式包括： (1) 確定起點的最短路徑問題一一即已知起始結(jié)點，求最短路徑問題。 (2) 確定終點的最短路徑問題一一與確定起點的問題相反，該問題是已知終結(jié)結(jié)點， 求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，再有向圖中該問題等同 于把所有路徑方向反轉(zhuǎn)的確定起點的問題。 (3) 確定起點終點的最短路徑問題

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

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

8、 些概念體系稱為模型。把邏輯應(yīng)用與模型的概念而得到的見解稱為理論。數(shù)學(xué)模型是各種模 型中最嚴密的模型。其正確性是通過邏輯和實踐來檢驗。20世紀數(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ù)型模型

9、、離散型模型、隨機型模型等。數(shù)學(xué)模型建立一般分為五 個階段： (1) 科學(xué)地識別與剖析實際問題； (2) 形成數(shù)學(xué)模型； (3) 求解數(shù)學(xué)問題； (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、；從第六站可以到 第五站和第七站，費用分別為10元和2元；從第七站可以到第九站，費用為4元從第八站 可以到第五站和第九站，費用分別為2元和3元；某人想從第一站到第八站去，求使總費 用最小的旅行路線。 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)集，邊上標注的數(shù)字表示邊的大小，邊的大小表示費用；箭頭指向的 結(jié)點為終止結(jié)點，沒有箭頭的邊表示這兩站之間相互通車，費用相同。 鄰接矩陣是表示頂點之間相鄰關(guān)系的矩

11、陣，設(shè)G=(V,E)是具有n個頂點的圖，則G的領(lǐng) v8 3 v9 接矩陣是具有如下性質(zhì)的n階方陣: A= (ajj) nXn 其中 ajj=O,若從Vj到vj無邊相連； ajj=w,若從Vj到Vj有邊相連且此邊的權(quán)為w； 矩陣的列表示的是起始結(jié)點；行表示的是終止結(jié)點；兩結(jié)點間如果相通，數(shù)字表示兩結(jié) 點間邊的大小，如果不相通，就沒有邊的大小，用“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矩陣的運算及其意義 表示兩結(jié)點之間長度為n的通路，這里的長度是指兩結(jié)點之間邊的數(shù)目。所以我們 要計算出An (n的取值為結(jié)點的個數(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后我們就可求出可達性矩陣， 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ù)(稱為這個點的標號)，它或者表示從vs到該點的最短路的權(quán)(稱為 P標號)、或者是從VS到該點的最短路的權(quán)的上界(稱為T標號

15、)，方法的每一步是去修改T 標號，并且把某一個具T標號的改變?yōu)榫逷標號的點，從而使G中具P標號的頂點數(shù)多一 個，這樣至多經(jīng)過n?l(n為圖G的頂點數(shù))步，就可以求出從vs到各點的最短路。 在敘述Dijkstra方法的具體步驟之前，以例1為例說明一下這個方法的基本思想。例 1中，s=lo因為所有Wij>0,故有d(vlz vl)=Oo這時，vl是具P標號的點。現(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)到達 v3,這時需要

16、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單位的費用，不管他如何再從v2

17、或從v3到達V4, 所需要的總費用都不會比1小(因為所有wij>0)o W而推知d(vl, v4) = l,這樣就可以使 v4變成具P標號的點?，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的最短路是(vl,

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

19、= O 對每一個 voVs,令 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。 ) < +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> 的 標 號 變 為 P 標 號 卩"叫)—"叫) 匚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)①，否則終止,這時對每一個 veSi, d(vs,

21、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=100; Type GraphType=Array[1?? MaxN, 1?? MaxN, ]of integer; 有向圖鄰接矩陣} Var w : GraphType; ｛圖G結(jié)構(gòu)，W[I, j]表示頂點i到j(luò)之間的費用｝ s, n, : integer; ｛s為源點，n為圖G的頂點

22、數(shù)｝ ｛存放從源點到任意頂點之間的最短路徑長度或其上界｝ D : array[1?? MaxN] of integer; SS : array[1.. MaxN] of boolean; ｛標有 P 標號的頂點集合｝ ｛p[i]存放最短路中頂點i的前面頂點編號｝ 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; ｛源點標上 p 標號｝ for i:=1 to n do if iOs then D[i]:二w[s, i]; D[s]:=0; k:=s; min:二T; While minOMaxint do ｛當存在所有T標號點的距離上界的最小值｝ Begin min:= Maxint; for j:=l to n do begin ｛在所有T標號點進行操作｝ 500) ｛this # resizcd=true;this? stylc. width=500;｝ > ｛如果j未標p標號，且到j(luò)

25、的路徑長度上界可更新，則更新為最小值｝ 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 ｛如果找到,則該點標上p標號｝ 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算法對應(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é)點子集s s = (i

27、nt *)malloc(sizeof(int) * n); //初始化最小路徑代價和前一跳節(jié)點值 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é)點作為最初的s子集 for (i = 1; i < n; i卄) f int temp = maxint; int u = v; 〃加入具有最小代價的鄰居節(jié)點到

28、s 了集 for (j = 1; j 〈二 n; j++) { if ((!s[j]) && (dist[j] < temp)) { u = j; temp = dist[j]; } } s[u] = 1; 〃計算加入新的節(jié)點后，更新路徑使得其產(chǎn)生代價最短 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;〃代價矩陣 int *dist;//最短路徑代價 int *prev;//前一跳節(jié)點空間 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)); } //輸入代價矩陣 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); } } } ////////////////// 程序運行結(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é)束語 參考文獻 [1]徐潔磐.離散數(shù)學(xué)導(dǎo)論一3版.北京:髙等教育岀版社,2004.6 ［2］謝永欽?試論信息與計算機科學(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.7 ［4］隴東學(xué)院教務(wù)處?教學(xué)計劃［ZJ.200L12