最短路徑分析的dijwsor算法

最短路徑分析的dijwsor算法

最短路徑分析是gis最基本的網(wǎng)絡(luò)分析功能。在求解最短路徑問(wèn)題的算法中,Dijkstra算法是目前國(guó)內(nèi)外一致公認(rèn)的較好算法?，F(xiàn)在許多計(jì)算機(jī)實(shí)現(xiàn)的算法都是在Dijkstra算法的基礎(chǔ)上,運(yùn)用關(guān)聯(lián)矩陣、鄰接矩陣的概念,使得存儲(chǔ)網(wǎng)絡(luò)數(shù)據(jù)和運(yùn)算,都需要定義N×N(N為網(wǎng)絡(luò)結(jié)點(diǎn)數(shù))的矩陣。當(dāng)網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)較大時(shí),將占用大量的存儲(chǔ)空間,并且運(yùn)算也很浪費(fèi)時(shí)間。徐立華(1989)提出最大相關(guān)邊數(shù)的概念,通過(guò)定義點(diǎn)-邊相關(guān)矩陣,節(jié)省了存儲(chǔ)空間,提高了運(yùn)算速度,為計(jì)算機(jī)解決大網(wǎng)絡(luò)問(wèn)題提供了切實(shí)可行的算法。作者在Dijkstra算法基礎(chǔ)上,對(duì)相關(guān)邊算法進(jìn)行改進(jìn),提出鄰接結(jié)點(diǎn)算法,進(jìn)一步提高運(yùn)算速度。1相鄰接收算法的基本概念1.1基于m條的最短路求解設(shè)已知圖中對(duì)總長(zhǎng)度來(lái)說(shuō)最接近于結(jié)點(diǎn)S的m個(gè)結(jié)點(diǎn),以及從結(jié)點(diǎn)S到這些結(jié)點(diǎn)中的每個(gè)結(jié)點(diǎn)的最短路。對(duì)結(jié)點(diǎn)S和這m個(gè)結(jié)點(diǎn)著色,然后最接近于S的第m+1個(gè)結(jié)點(diǎn)可這樣求——對(duì)于每個(gè)未著色的結(jié)點(diǎn),考慮所有已著色結(jié)點(diǎn)x,將弧(x,y)接在從S到x的最短路后面,從構(gòu)成的S到y(tǒng)的m條不同路中選出最短路,就是S到y(tǒng)的最短路。從m=0開(kāi)始,將此過(guò)程重復(fù)進(jìn)行,直至求得S到T的最短路為止。傳統(tǒng)的算法中應(yīng)用關(guān)聯(lián)矩陣和鄰接矩陣存儲(chǔ)網(wǎng)絡(luò)數(shù)據(jù),會(huì)有大量的無(wú)效的0元素或∞元素,占用大量存儲(chǔ)空間。在此基礎(chǔ)上進(jìn)行矩陣運(yùn)算,必將浪費(fèi)大量運(yùn)行時(shí)間。1.2用點(diǎn)-邊相關(guān)矩陣計(jì)算相關(guān)邊算法的關(guān)鍵是提出了最大相關(guān)邊數(shù)的概念,即一個(gè)網(wǎng)絡(luò)中各結(jié)點(diǎn)的相關(guān)邊數(shù)的最大值稱(chēng)為網(wǎng)絡(luò)的最大相關(guān)邊數(shù)。取網(wǎng)絡(luò)的最大相關(guān)邊數(shù)作為矩陣的列,網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)作為矩陣的行,構(gòu)造相關(guān)矩陣R,表示網(wǎng)絡(luò)結(jié)構(gòu)。相關(guān)矩陣的行按結(jié)點(diǎn)號(hào)從小到大順序排列,與結(jié)點(diǎn)i相關(guān)的邊的邊號(hào)寫(xiě)在矩陣的第i行。對(duì)照相關(guān)矩陣,把相關(guān)矩陣中各元素對(duì)應(yīng)的邊號(hào)的權(quán)值填在同一位置上,構(gòu)造相應(yīng)的初始判斷矩陣dR。有了相關(guān)矩陣R和初始判斷矩陣dR,根據(jù)Dijkstra算法的著色思想,就可以求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路徑了。關(guān)鍵步驟是,在dR已標(biāo)記的行中,求所有元素的最小值,并記下最小值的行和列。然后在R中取相同行列的元素,記為w,再在R的其它行中,尋找值為w的元素所在的行,將dR的對(duì)應(yīng)行作標(biāo)記。相關(guān)邊算法用點(diǎn)-邊相關(guān)矩陣描述網(wǎng)絡(luò)結(jié)構(gòu),大大減少無(wú)效的0元素和∞元素,從而節(jié)約存儲(chǔ)空間,提高運(yùn)算速度。但是當(dāng)網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)很多時(shí),在R的其它行中尋找長(zhǎng)值為w的元素的工作量也是很大的。為了進(jìn)一步提高運(yùn)行速度,可以對(duì)相關(guān)邊算法進(jìn)行改進(jìn)。1.3網(wǎng)收稿編碼的鄰接結(jié)論矩陣在最大相關(guān)邊數(shù)的啟發(fā)下,作者提出最大鄰接結(jié)點(diǎn)數(shù)的概念。一個(gè)網(wǎng)絡(luò)中,各結(jié)點(diǎn)的鄰接結(jié)點(diǎn)的最大值稱(chēng)為該網(wǎng)絡(luò)的最大鄰接結(jié)點(diǎn)數(shù)。取網(wǎng)絡(luò)的最大鄰接結(jié)點(diǎn)數(shù)作為矩陣的列,網(wǎng)絡(luò)的結(jié)點(diǎn)總數(shù)作為矩陣的行,構(gòu)造鄰接結(jié)點(diǎn)矩陣J來(lái)描述網(wǎng)收稿日期∶1997?10?21ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ絡(luò)結(jié)構(gòu)。鄰接結(jié)點(diǎn)矩陣的行按結(jié)點(diǎn)號(hào)從小到大順序排列,與結(jié)點(diǎn)i鄰接的結(jié)點(diǎn)號(hào)寫(xiě)在矩陣的第i行,如果結(jié)點(diǎn)i的鄰接結(jié)點(diǎn)數(shù)小于最大鄰接結(jié)點(diǎn)數(shù),則以0填充,直到填滿(mǎn)矩陣。對(duì)照鄰接結(jié)點(diǎn)矩陣,把鄰接結(jié)點(diǎn)矩陣中各元素鄰接關(guān)系對(duì)應(yīng)的邊的權(quán)值填在同一位置上(∞對(duì)應(yīng)0元素),構(gòu)造相應(yīng)的初始判斷矩陣dJ。鄰接結(jié)點(diǎn)矩陣J和相關(guān)矩陣R雖然占用存儲(chǔ)空間相等,但是鄰接結(jié)點(diǎn)矩陣為在計(jì)算機(jī)實(shí)現(xiàn)過(guò)程中進(jìn)一步提高運(yùn)算速度,提供了更加有效的網(wǎng)絡(luò)結(jié)構(gòu)組織方式。2實(shí)現(xiàn)接口算法的方法2.1種最短路徑為了使讀者了解鄰接結(jié)點(diǎn)算法求解最短路徑問(wèn)題的具體過(guò)程,現(xiàn)舉一例說(shuō)明(圖1)。1)從數(shù)據(jù)文件中裝載網(wǎng)絡(luò)數(shù)據(jù),網(wǎng)絡(luò)的結(jié)點(diǎn)和邊分別獲得計(jì)算機(jī)的內(nèi)部序號(hào)。需要說(shuō)明的是,網(wǎng)絡(luò)結(jié)點(diǎn)和邊的內(nèi)部序號(hào)和實(shí)際編號(hào),有可能不相同。為了增加算法的靈活性,算法使用內(nèi)部編號(hào)參與運(yùn)算。(這里假設(shè)內(nèi)部序號(hào)和實(shí)際編號(hào)相同)。2)求網(wǎng)絡(luò)的最大鄰接結(jié)點(diǎn)數(shù)m-iNodeNumMax。該網(wǎng)絡(luò)各結(jié)點(diǎn)的鄰接結(jié)點(diǎn)數(shù)的最大值m-iNodeNumMax=5。3)構(gòu)造鄰接結(jié)點(diǎn)矩陣m-pJ,各行中的結(jié)點(diǎn)序號(hào)可以前后隨意放置。對(duì)應(yīng)鄰接結(jié)點(diǎn)矩陣各元素,構(gòu)造初始判斷矩陣m-pDj。????????????????????2122153310854506367790360379105000709080000080000000????????????????????????????????????????1111108125151761412819∞51097166∞1010∞199161430∞∞∞15∞30∞7∞∞∞∞∞17∞∞∞∞∞∞∞????????????????????圖2鄰接結(jié)點(diǎn)矩陣和初始判斷矩陣4)有鄰接結(jié)點(diǎn)矩陣和初始判斷矩陣,就可以求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路徑。若起點(diǎn)S,終點(diǎn)為T(mén)。第一步,初始化標(biāo)記向量P,Pi=-1,i=1,2,…,m-iNodesNum,(m-iNodesNum為網(wǎng)絡(luò)結(jié)點(diǎn)總數(shù)):第二步,根據(jù)起點(diǎn)S,標(biāo)記初始判斷矩陣m-pDj的第S行,Ps=0,記最短距離m-fDistanceMin=0;第三步,根據(jù)終點(diǎn)T,判斷m-pDj的第T行是否已標(biāo)記,是則轉(zhuǎn)第五步,否則繼續(xù)。第四步,在m-pDj已標(biāo)記的行中,求所有元素的最小值dmin。若dmin=∞,說(shuō)明不存在最短路徑,則退出。否則m-fDistanceMin=dmin,記錄最小值元素的行di、列dj。然后在鄰接結(jié)點(diǎn)矩陣m-pJ中取(di,dj)元素,記為w。若第w行還未標(biāo)記,則將m-pDj的第w行標(biāo)記,Pw=di;并在m-pJ的第w行尋找值為di的元素,記錄該元素的行ri、列rj。將m-pDj剛獲得標(biāo)記的行中各元素值均加上m-fDistanceMin,并使m-pDj的(di,dj)和(ri,rj)元素為∞。轉(zhuǎn)第三步。第五步,從終點(diǎn)T開(kāi)始,由標(biāo)記向量P的分量循前點(diǎn),直到起點(diǎn)S,查得最短路徑m-pWays。m-fDistanceMin即為最短路徑距離。假設(shè)求結(jié)點(diǎn)1到結(jié)點(diǎn)7的最短路徑,過(guò)程如下。①初始化標(biāo)記向量P;②P=0,m-fDistanceMin=0;③在m-pDj已標(biāo)記的第1行中,dmin=11,di=1,dj=1,m-fDistanceMin=11;w=m-pJ=2,P=1,ri=2,rj=1;將m-pDj剛獲得標(biāo)記的第2行中各元素值均加上11,m-pDj=∞,m-pDj=∞;P=-1;④在m-pDj已標(biāo)記的第1行和第2行中,dmin=12,di=1,dj=2,m-fDistanceMin=12;w=m-pJ=5,P=1,ri=5,rj=1;將m-pDj剛獲得標(biāo)記的第5行中各元素值均加上12,m-pDj=∞,m-pDj=∞;P=-1;⑤在m-pDj已標(biāo)記的第1行、第2行和第5行中,dmin=17,di=5,dj=2,m-fDistanceMin=17;w=m-pJ=6,P=5,ri=6,rj=1;將m-pDj剛獲得標(biāo)記的第6行中各元素值均加上17,m-pDj=∞,m-pDj=∞;P=-1;⑥在m-pDj已標(biāo)記的第1行、第2行、第5行和第6行中,dmin=19,di=2,dj=2,m-fDistanceMin=19;w=m-pJ=4,P=2,ri=4,rj=1;將m-pDj獲得標(biāo)記的第4行中各元素值均加上19,m-pDj=∞,m-pDj=∞;P=-1;⑦在m-pDj已標(biāo)記的第1行、第2行、第4行、第5行和第6行中,dmin=21,di=2,dj=3,m-fDistanceMin=21;w=m-pJ=3,P=2,ri=3,rj=1;將m-pDj剛獲得標(biāo)記的第3行中各元素值均加上21,m-pDj=∞,m-pDj=∞;P=-1;⑧在m-pDj已標(biāo)記的第1行、第2行、第3行、第4行、第5行和第6行中,dmin=26,di=6,dj=3,m-fDistanceMin=26;w=m-pJ=7,P=6,ri=7,rj=2;將m-pDj剛獲得標(biāo)記的第7行中各元素值加上26,m-pDj=∞,m-pDj=∞;⑨P=6→P=5→P=1,m-pWays=(1,5,6,7),m-fDistanceMin=26。2.2最短路徑經(jīng)過(guò)邊串裝采用面向?qū)ο蟮姆椒?可以把網(wǎng)絡(luò)的最短路徑算法生成庫(kù)文件,以軟件模塊的形式提供給用戶(hù)。抽象的路徑類(lèi)描述如下。classCRoute{//成員變量protected:CHAIN*m-pChains;//網(wǎng)絡(luò)邊集指針intm-iChainsNum;//邊總數(shù)int*m-pPoints;//網(wǎng)絡(luò)結(jié)點(diǎn)集指針intm-iNodesNum;//結(jié)點(diǎn)總數(shù)intm-iNodeNumMax;//最大鄰接結(jié)點(diǎn)數(shù)float**m-pDj;//判斷矩陣指針int**m-pJ;//鄰接結(jié)點(diǎn)矩陣指針int*m-pWays;//最短路徑經(jīng)過(guò)邊串指針intm-iWayNum;//最短路徑經(jīng)過(guò)邊數(shù)floatm-fDistanceMin;//最短路徑距離BOOLm-bIsLoaded;//是否數(shù)據(jù)裝載成功//成員函數(shù)public:CRoute();//構(gòu)造函數(shù)～CRouts();//析構(gòu)函數(shù)public:BOOLLoadData(CStringstrPointFile,CStringstrLineFile);//數(shù)據(jù)裝載BOOLbest(intiSP,intiEP);//求起點(diǎn)到終點(diǎn)的最短路徑int*GetWay(int&iWayNum);//獲得最短路徑邊串voidGetDistance(float&fDistance){fDistance=m-fDistanceMin;}//獲得最短路徑距離protected:voidpntkrm();//求最大鄰接結(jié)點(diǎn)數(shù)voidarray();//構(gòu)造鄰接結(jié)點(diǎn)矩陣和初始判斷矩陣voidchain();//最短路徑經(jīng)過(guò)點(diǎn)串的鏈化};其中CHAIN是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)體,描述如下。typedefstruct{ints-iNo;//邊號(hào)ints-iSP;//始結(jié)點(diǎn)ints-iEP;//終結(jié)點(diǎn)floats-fLength//權(quán)值}CHAIN;作者已編寫(xiě)鄰接結(jié)點(diǎn)算法VC++程序,并用于某測(cè)繪勤務(wù)保障系統(tǒng)的最短路徑分析,取得了很好的效果。3節(jié)省運(yùn)行速度一般說(shuō)來(lái),網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)和邊數(shù)是影響計(jì)算機(jī)內(nèi)存和運(yùn)行速度的主要原因。在實(shí)際應(yīng)用中,復(fù)雜的網(wǎng)絡(luò)實(shí)體,可以根據(jù)具體情況盡量減少網(wǎng)