一種源頂點到其他各頂點所有路徑的算法及其Web服務設計

趙福生 （泉州師范學院數學與計算機科學學院，福建 泉州362000）

現實生活中，常常會碰到如下問題：某個城市的一個大公司在物流配送時，需要把貨物運送到全國的各個城市，如何選擇配送路徑，才能使得總的物流費用最小。解決這個實際問題所需要的決策參考信息是無向網中一個源頂點到其他各頂點的所有路徑。

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

求有向圖中源點到各結點所有路徑，毛紅梅與甘晟科提出了一種實用算法。該算法在求解源點到當前結點的所有路徑以前，必須求出源點到當前結點的所有逆鄰接頂點的所有路徑，該算法采用拓撲順序求各個所有路徑［3］。但該算法有一個不足的地方，只能求出有向圖中源點到各結點所有路徑。為此，筆者提出了求解一個源頂點到其他各頂點所有路徑問題的一種算法。

1 無向網

用圓圈表示城市，圓圈里面的數字為城市的編號。如果2個城市之間有路線可以到達的話，在2個頂點之間加上一條無向邊，無向邊上的數值為2個城市之間的距離。按照上述方法構造的圖為無向網。圖1所示為無向網的一個例子。

圖1 無向網的一個例子

2 源頂點到其他各頂點所有路徑計算的算法設計

2．1 算法采用的數據結構

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

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

其中，INF為符號常量，它的值為1000000000，VertexNumber為一個變量，里面的值為無向網的頂點個數。頂點0到頂點0的距離為0，a［0，0］存放0；頂點0到頂點1有直接路線相連距離為6，a［0，1］存放6；頂點0到頂點2有直接路線相連距離為5，a［0，2］存放5；……；頂點0到頂點5沒有直接路線相連，a［0，5］存放INF；頂點1到頂點0有直接路線相連距離為6，a［1，0］存放6；……

2）一維指針數組 源頂點到其他各頂點的所有路徑存放在圖3的結構中。L為一個一維指針數組，C＃定義如下：

其中，L［0］存放源頂點3到頂點0的所有路徑，L［1］存放源頂點3到頂點1的所有路徑，L［2］存放源頂點3到頂點2的所有路徑，L［4］存放源頂點3到頂點4的所有路徑，L［5］存放源頂點3到頂點5的所有路徑。L［1］里面的指針指向一個二維鏈表，二維鏈表的每個AllPathNode結點存放一條源頂點3到頂點1的路徑，AllPathNode結點的edgenumber成員存放路徑上的邊數，AllPathNode結點的distance成員存放路徑上的權值之和，AllPathNode結點的path成員指向一個一維鏈表，該一維鏈表存放路徑上的各個頂點的編號，頂點的編號存放在一維鏈表PathNode結點的vertex成員里面，AllPathNode結點的next成員指向下一個AllPathNode結點，二維鏈表里面的所有路徑按照路徑上的權值之和從小到大進行存放。

3）路徑樹 在查找所有路徑的過程中，需要建立一棵路徑樹，路徑樹中每個結點的結構如圖4所示，C＃定義如下：

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

其中，TreeNode結點的value成員存放當前頂點的編號；Tree-Node結點的distance成員存放源頂點到當前頂點的路徑上的權值之和；TreeNode結點的level成員存放源頂點到當前頂點的路徑上的邊的數目；TreeNode結點的firstchild成員指向當前結點的第一個孩子結點；TreeNode結點的parent成員指向當前結點的父親結點；Tree-Node結點的nextsibling成員指向當前結點的下一個兄弟結點。

2．2 算法設計

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

圖2 無向網的存儲結構

圖3 存放所有路徑的存儲結構

依次把第1層的各個頂點 （頂點0、頂點1、頂點2、頂點4）作為當前頂點，查找當前頂點的沒有在源頂點3到當前頂點的路徑中的所有鄰接頂點，把這些鄰接頂點按照頂點編號的順序依次作為當前頂點的孩子結點，這是路徑樹的第2層，同時把源頂點3到第2層頂點k的各個路徑加入到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 路徑樹中每個結點的結構

圖5 從源頂點3出發的路徑樹

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

3 所有路徑Web服務的設計

Web服務是通過后綴為．asmx的文件來提供的，．asmx文件里面的Web方法 ［WebMethod］public string ［］GraphAllPathFromOneVertexToAllVertex （int VertexNumber，string StringOfEdges，int SourceVertex）用來完成所有路徑的計算。

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

｛／／形參VertexNumber里面的值為頂點個數，形參StringOfEdges里面的值為邊的信息，形參SourceVertex里面的值為源頂點的編號。

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

4 Web服務的調試

針對圖1的無向網，Web服務調試時，VertexNumber文本框用來輸入頂點的個數 （6），String OfEdges文本框用來輸入頂點之間邊上的權值 （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文本框用來輸入源頂點的編號 （3）。輸入完以后，單擊 “調用”按鈕，可以得到源頂點3到其他各頂點的所有路徑如下：

頂點3到頂點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。

頂點3到頂點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。

頂點3到頂點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。

頂點3到頂點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。

頂點3到頂點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。

由上述求得的源頂點3到其他各頂點的所有路徑，可知筆者設計的Web服務是可行和有效的。

5 算法復雜度分析

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

T（n，m）=O（n！） （n為頂點個數；m為邊數）

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

S（n，m）=O（n！）

6 結 語

提出了求解一個源頂點到其他各頂點所有路徑問題的一種算法，設計所有路徑的Web服務，并完成Web服務的調試，運行結果找出了源頂點到其他各頂點的所有路徑，驗證了該算法的可行性和有效性。

［1］王桂平，王衍，任嘉辰 ．圖論算法理論、實現及應用 ［M］．北京：北京大學出版社，2011．

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

［3］毛紅梅，甘晟科 ．求有向圖中源點到各結點所有路徑的一種實用算法 ［J］．微電子學與計算機，2009，26（3）：128-130．

［4］孫強，楊宗源 ．求受頂點數限制的最短路徑問題的一個算法 ［J］．計算機工程，2002，28（9）：73-74．

［5］王衛強，孫強 ．求圖中受頂點數限制的所有最短路徑的算法 ［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服務集成的物流應急關鍵技術研究 ［D］．天津：天津大學，2012．