用C語(yǔ)言編程實(shí)現(xiàn)最短路徑摘 要：最短路徑問(wèn)題研究的問(wèn)題主要有：?jiǎn)卧醋疃搪窂絾?wèn)題、與所有頂點(diǎn)對(duì)之間 的最短路徑問(wèn)題。在我們的生產(chǎn)生活中遇到最短路徑的問(wèn)題實(shí)在太多了，比如乘汽車旅 行的人總希望找出到目的地盡可能的短的行程。如果有一張地圖并在圖上標(biāo)出每對(duì)十字 路口之間的距離，如何找出這一最短行程？我們首先應(yīng)該建立它的數(shù)學(xué)模型，借助圖、 矩陣等數(shù)學(xué)工具，然后根據(jù)數(shù)學(xué)模型寫出的算法及其源程序。關(guān)鍵詞：C語(yǔ)言，編程，最短路徑中圖分類號(hào)：G343Programs the realization most short-path wages hibiscuswith the C languageXinjinrong(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 shortpalh 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 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 shortpalh Chinese Libraryclassification number: G3431最短路徑及其相關(guān)概念最短路徑問(wèn)題是圖論研究中的-個(gè)經(jīng)典算法問(wèn)題，旨在尋找圖(由結(jié)點(diǎn)和路徑組成的) 中兩節(jié)點(diǎn)之間的最短路徑。算法具體的形式包括：(1) 確定起點(diǎn)的最短路徑問(wèn)題一一即已知起始結(jié)點(diǎn)，求最短路徑問(wèn)題。(2) 確定終點(diǎn)的最短路徑問(wèn)題一一與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終結(jié)結(jié)點(diǎn)， 求最短路徑的問(wèn)題。在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，再有向圖中該問(wèn)題等同 于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題。(3) 確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題一一即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。 最短路徑問(wèn)題研究的問(wèn)題主要有：?jiǎn)卧醋疃搪窂絾?wèn)題、與所有頂點(diǎn)對(duì)之間的最短路徑問(wèn) 題。1. 1最短路徑的基本概念1. 2與其相關(guān)的概念為了更好理解什么是最短路徑，首先我們就該清楚以下的問(wè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)生活中的應(yīng)用在我們的生產(chǎn)生活中遇到最短路徑的問(wèn)題實(shí)在太多了，比如乘汽車旅行的人總希望找出 到目的地盡可能的短的行程。如果有一張地圖并在圖上標(biāo)岀每對(duì)十字路口之間的距離，如何 找岀這一最短行程？種可能的方法就是枚舉岀所有路徑，并計(jì)算出每條路徑的長(zhǎng)度，然后選擇最短的條。 我們很容易看到，即使不考慮包含回路的路徑，依然存在數(shù)以萬(wàn)計(jì)的行千路線，而其屮絕大 多數(shù)是不值得考慮的。我們將闡明如何有效地解決這類問(wèn)題。在最短路徑問(wèn)題中，我們?nèi)绾螌⑽淖謹(jǐn)⑹鲛D(zhuǎn)換為 數(shù)學(xué)模型呢？3最短路徑的數(shù)學(xué)模型實(shí)現(xiàn)3.1數(shù)學(xué)模型數(shù)學(xué)模型是人們?yōu)榱肆私庵茑龅氖澜?，把口己的觀察及思想組織成概念體系。我們把這 些概念體系稱為模型。把邏輯應(yīng)用與模型的概念而得到的見(jiàn)解稱為理論。數(shù)學(xué)模型是各種模 型中最嚴(yán)密的模型。其正確性是通過(guò)邏輯和實(shí)踐來(lái)檢驗(yàn)。20世紀(jì)數(shù)學(xué)模型有了很大的發(fā)展。 其原因有三：一，數(shù)學(xué)理論的系統(tǒng)化，二，計(jì)算機(jī)的誕生，三，應(yīng)用數(shù)學(xué)的大發(fā)展。數(shù)學(xué)就是一個(gè)對(duì)未來(lái)作出預(yù)見(jiàn)的重要工具，它常常能以足夠的精確度對(duì)未來(lái)作出預(yù)見(jiàn), 告訴我們未來(lái)的發(fā)展趨勢(shì)。數(shù)學(xué)模型就像一張指示方向的交通圖，也像建筑的設(shè)計(jì)圖，雖然 簡(jiǎn)單卻切中要害。數(shù)學(xué)模型在各方面影響著我們。從大的方面講，財(cái)政預(yù)算，人口控制；從個(gè)人角度講, 以購(gòu)房為例，除去交預(yù)付款外，還要每刀扣除。這都需要數(shù)學(xué)模型的幫助。數(shù)學(xué)模型可以分為連續(xù)型模型、離散型模型、隨機(jī)型模型等。數(shù)學(xué)模型建立一般分為五 個(gè)階段：(1) 科學(xué)地識(shí)別與剖析實(shí)際問(wèn)題；(2) 形成數(shù)學(xué)模型；(3) 求解數(shù)學(xué)問(wèn)題；(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元；從第六站可以到 第五站和第七站，費(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)，沒(méi)有箭頭的邊表示這兩站之間相互通車，費(fèi)用相同。鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，則G的領(lǐng)v83v9接矩陣是具有如下性質(zhì)的n階方陣:A= (ajj) nXn其中ajj=O,若從Vj到vj無(wú)邊相連；ajj=w,若從Vj到Vj有邊相連且此邊的權(quán)為w；矩陣的列表示的是起始結(jié)點(diǎn)；行表示的是終止結(jié)點(diǎn)；兩結(jié)點(diǎn)間如果相通，數(shù)字表示兩結(jié)點(diǎn)間邊的大小，如果不相通，就沒(méi)有邊的大小，用“0”農(nóng)示。0 2 0 20 0 0 0A= 0 0 0 60 0 0 0000001000000000010000043061002000000420003000003. 2. 3矩陣的運(yùn)算及其意義表示兩結(jié)點(diǎn)之間長(zhǎng)度為n的通路，這里的長(zhǎng)度是指兩結(jié)點(diǎn)之間邊的數(shù)目。所以我們 要計(jì)算出An (n的取值為結(jié)點(diǎn)的個(gè)數(shù))。_063100000_06310000000001000000001000002020000002020000000000100000000010000000604306X00060430600001002000000100200()00000004000000004000020003000020003000000000_000000000_在求出A*1后我們就可求出可達(dá)性矩陣，Rn=A+A2+A3+.+An一個(gè)圖G的可達(dá)性矩陣給出了圖中各結(jié)點(diǎn)間是否可達(dá)以及圖中是否有回路。4 c語(yǔ)言編程實(shí)現(xiàn)4. 1算法的基本思想(數(shù)組實(shí)現(xiàn))4.1.1基本思想Dijkstra算法的基本思想是從從vs出發(fā)，逐步地向外探尋最短路。執(zhí)行過(guò)程中，與每 個(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))，方法的每一步是去修改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)過(guò)nl(n為圖G的頂點(diǎn)數(shù))步，就可以求出從vs到各點(diǎn)的最短路。在敘述Dijkstra方法的具體步驟之前，以例1為例說(shuō)明一下這個(gè)方法的基本思想。例 1中，s=lo因?yàn)樗蠾ij>0,故有d(vlz vl)=Oo這時(shí)，vl是具P標(biāo)號(hào)的點(diǎn)?，F(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í)需要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。 但如上所說(shuō)，這吋他已需要6單位或3單位的費(fèi)用，不管他如何再?gòu)膙2或從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, v3), d(vl, v3) = 3o這樣又可以使點(diǎn)v3變成具P標(biāo)號(hào)的點(diǎn), 如此重復(fù)這個(gè)過(guò)程，可以求出從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=0SO=Vs, P(Vs) = O A(Vs) = O對(duì)每一個(gè) voVs,令 T(v) = +8, A(v) = + oo, k=s開(kāi)始 如果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 = 500;"align = middle> ,貝9 把 500)thisresized=tTue;thissHc 宀一匚 align=middle> 的 標(biāo) 號(hào) 變 為 P 標(biāo) 號(hào) 卩"叫)"叫)匚am“心 ed=true;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)，否則終止,這時(shí)對(duì)每一個(gè) veSi, d(vs,v) = P(v), 而對(duì)每一個(gè)$"(匕v) - T(y) 500)this.resized=true;this.style.width = 500;" align = middle。4.1. 2算法的描敘過(guò)程Program Min Road Dijkstra;Const MaxN=100;Type GraphType=Array1 MaxN, 1 MaxN, of integer;有向圖鄰接矩陣Varw :GraphType; 圖G結(jié)構(gòu)，WI, j表示頂點(diǎn)i到j(luò)之間的費(fèi)用s, n, :integer; s為源點(diǎn)，n為圖G的頂點(diǎn)數(shù)存放從源點(diǎn)到任意頂點(diǎn)之間的最短路徑長(zhǎng)度或其上界D:array1MaxNofinteger;SS:array1.MaxNofboolean;標(biāo)有 P標(biāo)號(hào)的頂點(diǎn)集合pi存放最短路中頂點(diǎn)i的前面頂點(diǎn)編號(hào)p:array1.MaxNofinteger;Procedure Init;Var f :text;x, y, nw, I, j: integer;beginassign(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 算法過(guò)程var min, k, i, j, tempk:integer;beginfillchar(SS, sizeof(SS), 0);* 初始化* jSSs :=true;ps :=0; 源點(diǎn)標(biāo)上 p 標(biāo)號(hà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)號(hào)點(diǎn)的距離上界的最小值Beginmin:= 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ò)的路徑長(zhǎng)度上界可更新，則更新為最小值if (not ssj)and(wk, jOMaxint)and(dj>Dk+wk, j) then beginDj:= Dk+wk, j;Dj:二k;end;end;if n)in< Maxi nt then begin 如果找到,則該點(diǎn)標(biāo)上p標(biāo)號(hào)k:二temp;ssk:=true;end;end;end;Procedure Print; 打印出路徑var I,j:integer;temps,temppath:string;begin500)thisresized=true;this .stylewidth二500; “resized二true” >4. 2算法對(duì)應(yīng)的源程序# i nclude<stdio.h># i nelude <stdlib. h>/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)子集ss = (int *)malloc(sizeof(int) * n);/初始化最小路徑代價(jià)和前一跳節(jié)點(diǎn)值for (i = 1; i <= n; i卄)dist i = costv i;si = 0;if (disti = maxint)previ = 0;elseprevi = v;distv = 0;sv = 1;/源節(jié)點(diǎn)作為最初的s子集for (i = 1; i < n; i卄)fint temp = maxint;int u = v;加入具有最小代價(jià)的鄰居節(jié)點(diǎn)到s 了集for (j = 1; j 二 n; j+)if (!sj) && (distj < temp)u = j;temp = distj;su = 1;計(jì)算加入新的節(jié)點(diǎn)后，更新路徑使得其產(chǎn)生代價(jià)最短 for (j = 1; j 二 n; j+)if (!sjj) && (costuj < maxint) int newdist = distu + costuj; if (newdist < distj)dist j = newdist; prevj = u;/展示最佳路徑函數(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+;waycount = prevw;w = prevw;/輸出路徑printf("the best path is:n)；for (j = count; j >= 1; j-)printf (，z%d -> ", wayj);printf (dn", 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=(int. *)malloc(sizeof (int)*(n+1);for (i = 1; i <= n; i+)costi = (int *)malloc(sizeof(int)*(n+1);/輸入代價(jià)矩陣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 jkstra算法Di jkstra(n, v, dist, prev, cost);printf (have confirm the best pathn");printf("*n"); for(i = 1; i <= n ; i+)if(i!=v)printf (z，the distance cost from node %d to node %d is %dn/z, v, i, disti);printf (z，the pre-node of node %d is node %d n i, prcvi);ShowPath(n, v, i, dist, prev);/ 程序運(yùn)行結(jié)果:cT *D:orkSpacedj6DebugdjBe.exe*please input the node number： 6 please input the cost status: 0251 65535 655352032 65535 655355 3 0 3 1 512301 6553565535 65535 110265535 65535 5 65535 2 0please input the source node: 2have conf irn the best paththedistance cost fron node 2tonode1is2thepre-node of node 1 is node2thebest path is:2 -： 1thedistance cost fron node 2tonode3is3thepre-node of node 3 is node2thebest path is:2 -：> 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é)束語(yǔ)參考文獻(xiàn)1徐潔磐.離散數(shù)學(xué)導(dǎo)論一3版.北京:髙等教育岀版社,2004.62謝永欽試論信息與計(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.74隴東學(xué)院教務(wù)處教學(xué)計(jì)劃ZJ.200L12