基于矩陣運算K短路徑算法

趙禮峰，黃奕雯

(南京郵電大學 理學院，江蘇 南京 210046)

基于矩陣運算K短路徑算法

趙禮峰，黃奕雯

(南京郵電大學 理學院，江蘇 南京 210046)

最短路問題是復雜網絡中的經典問題，其求解算法層出不窮，各有優缺點。經典的算法包括Dijkstra算法、Ford算法和Floyd算法等，只能求解兩節點間的一條最短路徑。在實際生活中，還需要在大型網絡中限定一些前提條件求解兩點間次短、漸次短的路徑問題。為此，提出了一種對距離矩陣和路徑矩陣的迭代、替換算法，即從一個節點出發尋找其后繼節點，同時通過比較路徑長短得到兩點間最短路徑、次短路徑和漸次短路徑，并不斷重復、替換。為驗證所提算法的有效性，以一個大型網絡的應用作為實例，應用Matlab對所提算法進行了仿真實驗驗證。仿真結果表明，所提算法能夠在復雜大規模隨機網絡中滿足求解指定頂點間最短、次短和漸次短路徑的需要，具有較好的有效性和適用性。

次短路徑；漸次短路徑；距離矩陣；路徑矩陣

0 引 言

最短路徑問題是復雜網絡中一大經典問題，它的應用領域十分廣泛，如通信網絡、物流運輸、地理信息系統、軍事運籌學和旅行規劃等等[1]。經典算法[2]卻只能解決兩節點間一條最短路，而在這些實際運用中，往往不僅僅考慮一條最短路徑，還要根據實際情況及具體要求選擇其次短路徑、漸次短路徑。比如說在旅行線路的規劃問題上，所要選擇的路線不一定是距離最短的路線，還要考慮實際路況、天氣、經濟效益等因素，那么就需要篩選出不止一條短路徑。……