一種源頂點(diǎn)到其他各頂點(diǎn)所有路徑的算法及其Web服務(wù)設(shè)計(jì)

趙福生 （泉州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 泉州362000）

現(xiàn)實(shí)生活中，常常會(huì)碰到如下問題：某個(gè)城市的一個(gè)大公司在物流配送時(shí)，需要把貨物運(yùn)送到全國的各個(gè)城市，如何選擇配送路徑，才能使得總的物流費(fèi)用最小。解決這個(gè)實(shí)際問題所需要的決策參考信息是無向網(wǎng)中一個(gè)源頂點(diǎn)到其他各頂點(diǎn)的所有路徑。

目前，可以利用Dijkstra算法、Bellman-Ford算法和SPFA算法［1］求一個(gè)源頂點(diǎn)到其他各頂點(diǎn)的最短路徑問題；利用Floyd算法［1］求每對(duì)頂點(diǎn)間的最短路徑問題。求圖中每對(duì)頂點(diǎn)間的所有最短路徑，況超提出了3種算法：第1種算法是求圖中每對(duì)頂點(diǎn)間的所有最短路徑的基本算法，該算法適用于有向網(wǎng)與無向網(wǎng)，該算法通過逐步加入每條邊，并且同時(shí)判斷加入邊以后，每對(duì)頂點(diǎn)間的最短路徑是否有變化，若有變化，修改相應(yīng)的最短路徑，同時(shí)保存相應(yīng)的直接鄰接頂點(diǎn)的編號(hào)，最后通過最短路徑上直接鄰接頂點(diǎn)的編號(hào)生成每對(duì)頂點(diǎn)間的所有最短路徑；第2種算法是求圖中每對(duì)頂點(diǎn)間的所有最短路徑的改進(jìn)算法，該算法只適用于有向網(wǎng)。該算法先把出度為0的頂點(diǎn)入隊(duì)列，接下來得到一個(gè)出隊(duì)頂點(diǎn)，找到出隊(duì)頂點(diǎn)的一個(gè)逆鄰接頂點(diǎn)，把逆鄰接頂點(diǎn)的出度減1，如果逆鄰接頂點(diǎn)的出度為0，把逆鄰接頂點(diǎn)入隊(duì)列，同時(shí)判斷逆鄰接頂點(diǎn)到其他各頂點(diǎn)的最短路徑是否有變化。若有變化，保存最短路徑與直接鄰接頂點(diǎn)的編號(hào)，對(duì)于出隊(duì)頂點(diǎn)的每個(gè)逆鄰接頂點(diǎn)都進(jìn)行上述操作與判斷，對(duì)于每個(gè)出度為0的頂點(diǎn)也都要進(jìn)行上述操作，最后根據(jù)最短路徑上直接鄰接頂點(diǎn)的編號(hào)生成每對(duì)頂點(diǎn)間的所有最短路徑；第3種算法是求圖中受頂點(diǎn)數(shù)限制的每對(duì)頂點(diǎn)間的所有最短路徑的算法，該算法也是按照第2種算法求解最短路徑，找到的最短路徑上的頂點(diǎn)個(gè)數(shù)必須滿足給定的限制條件［2］。

求有向圖中源點(diǎn)到各結(jié)點(diǎn)所有路徑，毛紅梅與甘晟科提出了一種實(shí)用算法。該算法在求解源點(diǎn)到當(dāng)前結(jié)點(diǎn)的所有路徑以前，必須求出源點(diǎn)到當(dāng)前結(jié)點(diǎn)的所有逆鄰接頂點(diǎn)的所有路徑，該算法采用拓?fù)漤樞蚯蟾鱾€(gè)所有路徑［3］。但該算法有一個(gè)不足的地方，只能求出有向圖中源點(diǎn)到各結(jié)點(diǎn)所有路徑。為此，筆者提出了求解一個(gè)源頂點(diǎn)到其他各頂點(diǎn)所有路徑問題的一種算法。

1 無向網(wǎng)

用圓圈表示城市，圓圈里面的數(shù)字為城市的編號(hào)。如果2個(gè)城市之間有路線可以到達(dá)的話，在2個(gè)頂點(diǎn)之間加上一條無向邊，無向邊上的數(shù)值為2個(gè)城市之間的距離。按照上述方法構(gòu)造的圖為無向網(wǎng)。圖1所示為無向網(wǎng)的一個(gè)例子。

圖1 無向網(wǎng)的一個(gè)例子

2 源頂點(diǎn)到其他各頂點(diǎn)所有路徑計(jì)算的算法設(shè)計(jì)

2．1 算法采用的數(shù)據(jù)結(jié)構(gòu)

1）二維數(shù)組 圖1所示的無向網(wǎng)采用圖2所示的二維數(shù)組a來存放。二維數(shù)組a的C＃定義如下：

const int INF=1000000000；int［，］a=new int［VertexNumber，VertexNumber］；

其中，INF為符號(hào)常量，它的值為1000000000，VertexNumber為一個(gè)變量，里面的值為無向網(wǎng)的頂點(diǎn)個(gè)數(shù)。頂點(diǎn)0到頂點(diǎn)0的距離為0，a［0，0］存放0；頂點(diǎn)0到頂點(diǎn)1有直接路線相連距離為6，a［0，1］存放6；頂點(diǎn)0到頂點(diǎn)2有直接路線相連距離為5，a［0，2］存放5；……；頂點(diǎn)0到頂點(diǎn)5沒有直接路線相連，a［0，5］存放INF；頂點(diǎn)1到頂點(diǎn)0有直接路線相連距離為6，a［1，0］存放6；……

2）一維指針數(shù)組 源頂點(diǎn)到其他各頂點(diǎn)的所有路徑存放在圖3的結(jié)構(gòu)中。L為一個(gè)一維指針數(shù)組，C＃定義如下：

其中，L［0］存放源頂點(diǎn)3到頂點(diǎn)0的所有路徑，L［1］存放源頂點(diǎn)3到頂點(diǎn)1的所有路徑，L［2］存放源頂點(diǎn)3到頂點(diǎn)2的所有路徑，L［4］存放源頂點(diǎn)3到頂點(diǎn)4的所有路徑，L［5］存放源頂點(diǎn)3到頂點(diǎn)5的所有路徑。L［1］里面的指針指向一個(gè)二維鏈表，二維鏈表的每個(gè)AllPathNode結(jié)點(diǎn)存放一條源頂點(diǎn)3到頂點(diǎn)1的路徑，AllPathNode結(jié)點(diǎn)的edgenumber成員存放路徑上的邊數(shù)，AllPathNode結(jié)點(diǎn)的distance成員存放路徑上的權(quán)值之和，AllPathNode結(jié)點(diǎn)的path成員指向一個(gè)一維鏈表，該一維鏈表存放路徑上的各個(gè)頂點(diǎn)的編號(hào)，頂點(diǎn)的編號(hào)存放在一維鏈表PathNode結(jié)點(diǎn)的vertex成員里面，AllPathNode結(jié)點(diǎn)的next成員指向下一個(gè)AllPathNode結(jié)點(diǎn)，二維鏈表里面的所有路徑按照路徑上的權(quán)值之和從小到大進(jìn)行存放。

3）路徑樹 在查找所有路徑的過程中，需要建立一棵路徑樹，路徑樹中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)如圖4所示，C＃定義如下：

class TreeNode ｛public TreeNode firstchild；public int level；public int value；public int distance；public TreeNode parent；public TreeNode nextsibling；｝

其中，TreeNode結(jié)點(diǎn)的value成員存放當(dāng)前頂點(diǎn)的編號(hào)；Tree-Node結(jié)點(diǎn)的distance成員存放源頂點(diǎn)到當(dāng)前頂點(diǎn)的路徑上的權(quán)值之和；TreeNode結(jié)點(diǎn)的level成員存放源頂點(diǎn)到當(dāng)前頂點(diǎn)的路徑上的邊的數(shù)目；TreeNode結(jié)點(diǎn)的firstchild成員指向當(dāng)前結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)；TreeNode結(jié)點(diǎn)的parent成員指向當(dāng)前結(jié)點(diǎn)的父親結(jié)點(diǎn)；Tree-Node結(jié)點(diǎn)的nextsibling成員指向當(dāng)前結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。

2．2 算法設(shè)計(jì)

該算法利用路徑樹來查找源頂點(diǎn)到其他各頂點(diǎn)的所有路徑。源頂點(diǎn)3為路徑樹的根結(jié)點(diǎn) （路徑樹的第0層），把源頂點(diǎn)3的所有鄰接頂點(diǎn) （頂點(diǎn)0、頂點(diǎn)1、頂點(diǎn)2、頂點(diǎn)4）按照頂點(diǎn)編號(hào)的順序依次作為源頂點(diǎn)3的孩子結(jié)點(diǎn)，這是路徑樹的第1層，同時(shí)把路徑3-0加入到L［0］里面合適的位置，把路徑3-1加入到L［1］里面合適的位置，把路徑3-2加入到L［2］里面合適的位置，把路徑3-4加入到L［4］里面合適的位置。

圖2 無向網(wǎng)的存儲(chǔ)結(jié)構(gòu)

圖3 存放所有路徑的存儲(chǔ)結(jié)構(gòu)

依次把第1層的各個(gè)頂點(diǎn) （頂點(diǎn)0、頂點(diǎn)1、頂點(diǎn)2、頂點(diǎn)4）作為當(dāng)前頂點(diǎn)，查找當(dāng)前頂點(diǎn)的沒有在源頂點(diǎn)3到當(dāng)前頂點(diǎn)的路徑中的所有鄰接頂點(diǎn)，把這些鄰接頂點(diǎn)按照頂點(diǎn)編號(hào)的順序依次作為當(dāng)前頂點(diǎn)的孩子結(jié)點(diǎn)，這是路徑樹的第2層，同時(shí)把源頂點(diǎn)3到第2層頂點(diǎn)k的各個(gè)路徑加入到L［k］里面合適的位置，比如路徑3-0-1加入到L［1］里面合適的位置，路徑3-0-2加入到L［2］里面合適的位置，路徑3-0-4加入到L［4］里面合適的位置，路徑3-1-0加入到L［0］里面合適的位置，路徑3-1-2加入到L［2］里面合適的位置，路徑3-1-4加入到L［4］里面合適的位置，路徑3-2-0加入到L［0］里面合適的位置，路徑3-2-1加入到L［1］里面合適的位置，路徑3-2-4加入到L［4］里面合適的位置，路徑3-2-5加入到L［5］里面合適的位置，路徑3-4-0加入到L［0］里面合適的位置，路徑3-4-1加入到L［1］里面合適的位置，路徑3-4-2加入到L［2］里面合適的位置。

圖4 路徑樹中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)

圖5 從源頂點(diǎn)3出發(fā)的路徑樹

依次把第2層的各個(gè)頂點(diǎn)作為當(dāng)前頂點(diǎn)，進(jìn)行上述操作。按照上述方法從上到下從左到右構(gòu)造的路徑樹如圖5所示。路徑樹構(gòu)造完以后，L［k］里面存放源頂點(diǎn)3到頂點(diǎn)k的所有路徑，而且，這些所有路徑在L［k］里面按照權(quán)值之和從小到大進(jìn)行存放。

3 所有路徑Web服務(wù)的設(shè)計(jì)

Web服務(wù)是通過后綴為．a(chǎn)smx的文件來提供的，．a(chǎn)smx文件里面的Web方法 ［WebMethod］public string ［］GraphAllPathFromOneVertexToAllVertex （int VertexNumber，string StringOfEdges，int SourceVertex）用來完成所有路徑的計(jì)算。

public string ［］GraphAllPathFromOneVertexToAllVertex （int VertexNumber，string StringOfEdges，int SourceVertex）

｛／／形參VertexNumber里面的值為頂點(diǎn)個(gè)數(shù)，形參StringOfEdges里面的值為邊的信息，形參SourceVertex里面的值為源頂點(diǎn)的編號(hào)。

其中k=FirstAdjacentVertex （VertexNumber，a，p．value）函數(shù)用來求p．value的第一個(gè)鄰接頂點(diǎn)；k=NextAdjacentVertex （VertexNumber，a，p．value，k）函數(shù)用來求p．value的相對(duì)于鄰接頂點(diǎn)k的下一個(gè)鄰接頂點(diǎn)；TreepContaink（T，p，k）函數(shù)用來判斷樹根結(jié)點(diǎn)到p指向結(jié)點(diǎn)路徑中是否存在頂點(diǎn)k，存在，返回值true；不存在，返回值false；AddPath（T，r，L［k］，a）；函數(shù)用來把樹根結(jié)點(diǎn)到r指向結(jié)點(diǎn)這一條路徑加入到L［k］指向的二維鏈表合適的位置。

4 Web服務(wù)的調(diào)試

針對(duì)圖1的無向網(wǎng)，Web服務(wù)調(diào)試時(shí)，VertexNumber文本框用來輸入頂點(diǎn)的個(gè)數(shù) （6），String OfEdges文本框用來輸入頂點(diǎn)之間邊上的權(quán)值 （0 6 5 3 4INF 6 0 2 7 6INF 5 2 0 3 9 8 3 7 3 0 5INF 4 6 9 5 0INF INF INF 8INF INF 0），SourceVertex文本框用來輸入源頂點(diǎn)的編號(hào) （3）。輸入完以后，單擊 “調(diào)用”按鈕，可以得到源頂點(diǎn)3到其他各頂點(diǎn)的所有路徑如下：

頂點(diǎn)3到頂點(diǎn)0的所有路徑為：3：3-0、8：3-2-0、9：3-4-0、11：3-2-1-0、13：3-1-0、14：3-1-2-0、15：3-2-1-4-0、16：3-2-4-0、17：3-1-4-0、17：3-4-1-0、18：3-4-1-2-0、19：3-4-2-0、22：3-1-2-4-0、22：3-4-2-1-0、24：3-2-4-1-0、27：3-1-4-2-0。

頂點(diǎn)3到頂點(diǎn)1的所有路徑為：5：3-2-1、7：3-1、9：3-0-1、10：3-0-2-111：3-4-1、13：3-0-4-1、14：3-2-0-1、15：3-4-0-1、16：3-4-2-1、16：3-4-0-2-1、8：3-2-4-1、18：3-0-4-2-1、18：3-2-0-4-1、22：3-2-4-0-1、23：3-0-2-4-1、25：3-4-2-0-1。

頂點(diǎn)3到頂點(diǎn)2的所有路徑為：3：3-2、8：3-0-2、9：3-1-2、11：3-0-1-2、13：3-4-1-2、14：3-4-2、14：3-4-0-2、15：3-0-4-1-2、16：3-0-4-2、17：3-4-0-1-2、18：3-1-0-2、22：3-1-4-2、22：3-1-4-0-2、22：3-4-1-0-2、24：3-0-1-4-2、26：3-1-0-4-2。

頂點(diǎn)3到頂點(diǎn)4的所有路徑為：5：3-4、7：3-0-4、11：3-2-1-4、12：3-2-4、12：3-2-0-4、13：3-1-4、15：3-0-1-4、15：3-2-1-0-4、16：3-0-2-1-4、17：3-0-2-4、17：3-1-0-4、18：3-1-2-4、18：3-1-2-0-4、20：3-0-1-2-4、20：3-2-0-1-4、27：3-1-0-2-4。

頂點(diǎn)3到頂點(diǎn)5的所有路徑為：11：3-2-5、16：3-0-2-5、17：3-1-2-5、19：3-0-1-2-5、21：3-4-1-2-5、22：3-4-2-5、22：3-4-0-2-5、23：3-0-4-1-2-5、24：3-0-4-2-5、25：3-4-0-1-2-5、26：3-1-0-2-5、30：3-1-4-2-5、30：3-1-4-0-2-5、30：3-4-1-0-2-5、32：3-0-1-4-2-5、34：3-1-0-4-2-5。

由上述求得的源頂點(diǎn)3到其他各頂點(diǎn)的所有路徑，可知筆者設(shè)計(jì)的Web服務(wù)是可行和有效的。

5 算法復(fù)雜度分析

筆者提出的算法適用于所有的無向網(wǎng)。對(duì)于每個(gè)無向網(wǎng)，出現(xiàn)的概率不相等，因此，不能求平均情況下的時(shí)間復(fù)雜度與空間復(fù)雜度，只能求最壞情況下的時(shí)間復(fù)雜度與空間復(fù)雜度，從而估算執(zhí)行時(shí)間增長率的一個(gè)上界與所需存儲(chǔ)空間增長率的一個(gè)上界。最壞情況的無向網(wǎng)為：每個(gè)頂點(diǎn)到其他頂點(diǎn)都有邊。這時(shí)，整個(gè)算法所需要的時(shí)間T（n，m）隨問題規(guī)模n的增大而增大，增長率與n！大概相同，因此，最壞情況下，該算法的時(shí)間復(fù)雜度為：

T（n，m）=O（n?。?（n為頂點(diǎn)個(gè)數(shù)；m為邊數(shù)）

這時(shí)，整個(gè)算法所需要的存儲(chǔ)空間S（n，m）隨問題規(guī)模n的增大而增大，增長率與n！大概相同，因此，最壞情況下，該算法的空間復(fù)雜度為：

S（n，m）=O（n?。?/p>

6 結(jié) 語

提出了求解一個(gè)源頂點(diǎn)到其他各頂點(diǎn)所有路徑問題的一種算法，設(shè)計(jì)所有路徑的Web服務(wù)，并完成Web服務(wù)的調(diào)試，運(yùn)行結(jié)果找出了源頂點(diǎn)到其他各頂點(diǎn)的所有路徑，驗(yàn)證了該算法的可行性和有效性。

［1］王桂平，王衍，任嘉辰 ．圖論算法理論、實(shí)現(xiàn)及應(yīng)用 ［M］．北京：北京大學(xué)出版社，2011．

［2］況超 ．求圖中每對(duì)頂點(diǎn)間的所有最短路徑算法的分析與研究 ［D］．上海：華東師范大學(xué)，2011．

［3］毛紅梅，甘晟科 ．求有向圖中源點(diǎn)到各結(jié)點(diǎn)所有路徑的一種實(shí)用算法 ［J］．微電子學(xué)與計(jì)算機(jī)，2009，26（3）：128-130．

［4］孫強(qiáng)，楊宗源 ．求受頂點(diǎn)數(shù)限制的最短路徑問題的一個(gè)算法 ［J］．計(jì)算機(jī)工程，2002，28（9）：73-74．

［5］王衛(wèi)強(qiáng)，孫強(qiáng) ．求圖中受頂點(diǎn)數(shù)限制的所有最短路徑的算法 ［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（7）：1754-1757．

［6］LI Guang-ru，HU Jing-feng，Sun Zhi．Structure and algorithm design of the manager agent in WebGIS ［A］．IEEE Proceedings of the Fifth International Conference on Machine Learning and Cybernetics ［C］ ．Dalian：IEEE Computer Society，2006：40-45．

［7］王澤來 ．基于Web服務(wù)集成的物流應(yīng)急關(guān)鍵技術(shù)研究 ［D］．天津：天津大學(xué)，2012．