【摘要】：針對如何在無回路有向連通圖中求解k階最短路問題,提出了新的思路,即先求出某路徑與最短路的長度之差,再利用該差值求得該路徑。在該思路的指引下,提出了新的參數(shù)概念,如點參數(shù)N、弧參數(shù)A以及終點的特征參數(shù)θ,并給出了這些參數(shù)的計算方法;揭示了這些參數(shù)與圖中相應路徑之間的關系,推導出點參數(shù)N定理和弧參數(shù)A定理;利用這些參數(shù)和定理,設計出在無回路有向連通圖中求解k階最短路問題的多項式算法,證明了算法的正確性,并且經(jīng)過分析,該算法的復雜度為O(km),m表示弧數(shù);最后,通過應用舉例對該算法進行了演示。
[Abstract]:In order to solve the problem of k order shortest path in an undirected connected graph, a new idea is put forward, that is, the difference between the length of a path and the shortest path is obtained first, and then the path is obtained by using the difference. Under the guidance of this idea, a new concept of parameters, such as point parameter N, arc parameter A and the characteristic parameter 胃 of the end point, is put forward, and the calculation method of these parameters is given. The relationship between these parameters and the corresponding paths in the graph is revealed, and the point parameter N theorem and arc parameter A theorem are derived. By using these parameters and theorems, a polynomial algorithm for solving k order shortest path problem in an unloop directed connected graph is designed. The correctness of the algorithm is proved, and the complexity of the algorithm is O (km), m to represent the number of arcs. Finally, an example is given to demonstrate the algorithm.
【作者單位】： 南昌工程學院工商管理學院;華北電力大學經(jīng)濟與管理學院;
【基金】：國家自然科學基金資助項目(71171079) 江西省高校人文社會科學項目(GL1591)
【分類號】：TP301.6

【參考文獻】

相關期刊論文 前7條

1 乞建勛;蘇志雄;張立輝;;無向正權網(wǎng)絡最短路模型的建立和理論分析[J];系統(tǒng)工程理論與實踐;2012年10期

2 劉建美;馬壽峰;馬帥奇;;基于改進的Dijkstra算法的動態(tài)最短路計算方法[J];系統(tǒng)工程理論與實踐;2011年06期

3 李星梅;乞建勛;蘇志雄;;自由時差定理與k階次關鍵路線的求法[J];管理科學學報;2009年02期

4 魏航;;一種求解時變條件下有宵禁限制最短路的算法[J];管理科學學報;2009年01期

5 高松;陸鋒;段瀅瀅;;一種基于雙向搜索的K則最優(yōu)路徑算法[J];武漢大學學報(信息科學版);2008年04期

6 魏航;;時變條件下允許等待的最短路問題[J];系統(tǒng)管理學報;2008年01期

7 李杰;劉思峰;任盈盈;賈迎賓;商紅巖;;Kth最短路徑的Bellman改進算法[J];數(shù)學的實踐與認識;2006年01期

【共引文獻】

相關期刊論文 前10條

1 左秀峰;沈萬杰;;基于Floyd算法的多重最短路問題的改進算法[J];計算機科學;2017年05期

2 王旭坪;韓進軍;董杰;;考慮脆弱點的成品油二次配送風險層級優(yōu)化[J];管理學報;2017年05期

3 盧國菊;高彩軍;;礦井災變時期最優(yōu)避災路徑研究[J];礦業(yè)安全與環(huán)保;2017年02期

4 蘇志雄;乞建勛;魏漢英;;求解無回路有向連通圖中的k階最短路問題[J];系統(tǒng)管理學報;2017年02期

5 張靜文;喬傳卓;劉耕濤;;基于魯棒性的關鍵鏈二次資源沖突消除策略[J];管理科學學報;2017年03期

6 趙欣;陳珊珊;;基于多智能體系統(tǒng)的應急車輛路徑誘導策略研究[J];物流技術;2016年10期

7 王敬敏;周維維;;基于節(jié)點時差特性的CPM網(wǎng)絡次關鍵路線的簡單算法[J];運籌與管理;2016年05期

8 郭文鑫;向德軍;王彬;湯磊;余志文;;基于K-means聚類和信息論的電力系統(tǒng)安全信息特征選擇[J];電力信息與通信技術;2016年10期

9 羅雅麗;;基于三改四化后常德動態(tài)路網(wǎng)模型的改進遺傳算法的研究[J];電腦編程技巧與維護;2016年17期

10 靳國偉;何世偉;黎浩東;何必勝;殷瑋川;;Harmony Search-Dijkstra混合算法在鐵路物流中心分層選址中的應用[J];北京交通大學學報;2016年04期

【二級參考文獻】

相關期刊論文 前10條

1 盧照;師軍;;并行最短路徑搜索算法的設計與實現(xiàn)[J];計算機工程與應用;2010年03期

2 鄭龍;周經(jīng)倫;易凡;陳玉教;;大規(guī)模隨機運輸網(wǎng)絡的路徑優(yōu)化[J];系統(tǒng)工程理論與實踐;2009年10期

3 王正武;羅大庸;黃中祥;王一軍;;不確定性條件下的多目標多路徑選擇[J];系統(tǒng)工程學報;2009年03期

4 魏航;;時變隨機網(wǎng)絡下有時間窗的有害物品運輸路徑選擇研究[J];中國管理科學;2009年03期

5 蘇志雄;李星梅;乞建勛;;基于CPM原理和Dijkstra算法的SPM網(wǎng)絡計劃模型及性質[J];運籌與管理;2008年01期

6 林浩;皮軍德;;有向網(wǎng)絡上單源多匯的最優(yōu)連接問題[J];系統(tǒng)工程學報;2008年01期

7 王素欣;高利;崔小光;陳雪梅;;多集散點車輛路徑問題及其蟻群算法研究[J];系統(tǒng)工程理論與實踐;2008年02期

8 韓麗霞;王宇平;;解旅行商問題的一個新的遺傳算法[J];系統(tǒng)工程理論與實踐;2007年12期

9 劉桂枝;高太平;;帶二次參數(shù)賦權的多階段網(wǎng)絡最短路算法[J];系統(tǒng)工程理論與實踐;2007年07期

10 魏航;李軍;魏潔;;時變條件下有宵禁限制的有害物品運輸最短路研究[J];管理工程學報;2007年03期

【相似文獻】

相關期刊論文 前10條

1 汪澤焱,刁興春,汪挺;帶均勻分布權值的最短路問題[J];計算機工程與應用;2005年17期

2 高尚;楊靜宇;;最短路的蟻群算法收斂性分析[J];科學技術與工程;2006年03期

3 何彩香;姜秀燕;施冰;;有宵禁限制的時間最短路[J];大理學院學報(自然科學);2006年06期

4 陳建芳;;一種求解時變條件下雙目標最短路的算法[J];浙江科技學院學報;2006年04期

5 李睿;楊子蘭;;限制性最短路問題[J];計算機與信息技術;2012年02期

6 張?zhí)熹?通過平面上幾個定點的最短路[J];福州大學學報(自然科學版);1986年01期

7 李仁豪;;賦有權向量網(wǎng)絡的2-范數(shù)意義下的最短路[J];山東礦業(yè)學院學報;1990年02期

8 郭強;;Hopfield神經(jīng)網(wǎng)絡結構在最短路問題中的應用[J];西安電子科技大學學報;1996年S1期

9 宋恩民,黃文奇,劉宏,李海山;含負權有向網(wǎng)絡中最短路問題的求解算法[J];華中理工大學學報;1997年S1期

10 劉胤宏;含參數(shù)的最短路問題及其原始—對偶算法[J];湘潭師范學院學報(社會科學版);1999年06期

相關會議論文 前4條

1 袁二明;李瑩;李彪;;基于交通擁堵預測的交通網(wǎng)絡最短路問題的研究[A];“兩型社會”建設與管理創(chuàng)新——第十五屆中國管理科學學術年會論文集（上）[C];2013年

2 施欣;;隨機運輸網(wǎng)絡最短路分布研究[A];復雜巨系統(tǒng)理論·方法·應用——中國系統(tǒng)工程學會第八屆學術年會論文集[C];1994年

3 朱建明;沙丹;;時變網(wǎng)絡中任意等待時間最短路問題的一個對偶算法(英文)[A];第四屆中國智能計算大會論文集[C];2010年

4 牛宏睿;李平;史天運;;應急資源調度中最短路邊權不確定性問題的建模與仿真[A];2009年中國智能自動化會議論文集（第七分冊）[南京理工大學學報（增刊）][C];2009年

相關博士學位論文 前2條

1 吳六三;基于網(wǎng)絡熵的網(wǎng)絡可靠性研究[D];南京航空航天大學;2014年

2 高原;不確定圖與不確定網(wǎng)絡[D];清華大學;2013年

相關碩士學位論文 前9條

1 魏翔宇;面向最短路的網(wǎng)絡阻斷問題研究[D];國防科學技術大學;2014年

2 蘇健;自動波方法求解TSP問題[D];西安電子科技大學;2004年

3 雷芬;隨機網(wǎng)絡中的動態(tài)最短路研究[D];中央民族大學;2009年

4 張振抻;網(wǎng)絡最短路的解集結構及有關問題[D];鄭州大學;2002年

5 張美玲;最短路問題的一個改進蟻群算法[D];蘭州大學;2008年

6 陶娜娜;模糊隨機多屬性最短路問題[D];南京理工大學;2006年

7 臺偉英;幾類網(wǎng)絡改進問題的算法及復雜性[D];中國計量學院;2012年

8 劉桂枝;帶二次參數(shù)賦權多階段網(wǎng)絡的最短路問題研究[D];山西大學;2007年

9 張建勇;網(wǎng)絡的K最短路分析與應用[D];山東科技大學;2006年

，

本文編號：2339757