求解无回路有向连通图中的k阶最短路问题

发布时间：2018-11-18 10:13

【摘要】：针对如何在无回路有向连通图中求解k阶最短路问题,提出了新的思路,即先求出某路径与最短路的长度之差,再利用该差值求得该路径。在该思路的指引下,提出了新的参数概念,如点参数N、弧参数A以及终点的特征参数θ,并给出了这些参数的计算方法;揭示了这些参数与图中相应路径之间的关系,推导出点参数N定理和弧参数A定理;利用这些参数和定理,设计出在无回路有向连通图中求解k阶最短路问题的多项式算法,证明了算法的正确性,并且经过分析,该算法的复杂度为O(km),m表示弧数;最后,通过应用举例对该算法进行了演示。
[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.
【作者单位】： 南昌工程学院工商管理学院;华北电力大学经济与管理学院;
【基金】：国家自然科学基金资助项目(71171079) 江西省高校人文社会科学项目(GL1591)
【分类号】：TP301.6

【参考文献】

相关期刊论文 前7条

1 乞建勋;苏志雄;张立辉;;无向正权网络最短路模型的建立和理论分析[J];系统工程理论与实践;2012年10期

2 刘建美;马寿峰;马帅奇;;基于改进的Dijkstra算法的动态最短路计算方法[J];系统工程理论与实践;2011年06期

3 李星梅;乞建勋;苏志雄;;自由时差定理与k阶次关键路线的求法[J];管理科学学报;2009年02期

4 魏航;;一种求解时变条件下有宵禁限制最短路的算法[J];管理科学学报;2009年01期

5 高松;陆锋;段滢滢;;一种基于双向搜索的K则最优路径算法[J];武汉大学学报(信息科学版);2008年04期

6 魏航;;时变条件下允许等待的最短路问题[J];系统管理学报;2008年01期

7 李杰;刘思峰;任盈盈;贾迎宾;商红岩;;Kth最短路径的Bellman改进算法[J];数学的实践与认识;2006年01期

【共引文献】

相关期刊论文 前10条

1 左秀峰;沈万杰;;基于Floyd算法的多重最短路问题的改进算法[J];计算机科学;2017年05期

2 王旭坪;韩进军;董杰;;考虑脆弱点的成品油二次配送风险层级优化[J];管理学报;2017年05期

3 卢国菊;高彩军;;矿井灾变时期最优避灾路径研究[J];矿业安全与环保;2017年02期

4 苏志雄;乞建勋;魏汉英;;求解无回路有向连通图中的k阶最短路问题[J];系统管理学报;2017年02期

5 张静文;乔传卓;刘耕涛;;基于鲁棒性的关键链二次资源冲突消除策略[J];管理科学学报;2017年03期

6 赵欣;陈珊珊;;基于多智能体系统的应急车辆路径诱导策略研究[J];物流技术;2016年10期

7 王敬敏;周维维;;基于节点时差特性的CPM网络次关键路线的简单算法[J];运筹与管理;2016年05期

8 郭文鑫;向德军;王彬;汤磊;余志文;;基于K-means聚类和信息论的电力系统安全信息特征选择[J];电力信息与通信技术;2016年10期

9 罗雅丽;;基于三改四化后常德动态路网模型的改进遗传算法的研究[J];电脑编程技巧与维护;2016年17期

10 靳国伟;何世伟;黎浩东;何必胜;殷玮川;;Harmony Search-Dijkstra混合算法在铁路物流中心分层选址中的应用[J];北京交通大学学报;2016年04期

【二级参考文献】

相关期刊论文 前10条

1 卢照;师军;;并行最短路径搜索算法的设计与实现[J];计算机工程与应用;2010年03期

2 郑龙;周经伦;易凡;陈玉教;;大规模随机运输网络的路径优化[J];系统工程理论与实践;2009年10期

3 王正武;罗大庸;黄中祥;王一军;;不确定性条件下的多目标多路径选择[J];系统工程学报;2009年03期

4 魏航;;时变随机网络下有时间窗的有害物品运输路径选择研究[J];中国管理科学;2009年03期

5 苏志雄;李星梅;乞建勋;;基于CPM原理和Dijkstra算法的SPM网络计划模型及性质[J];运筹与管理;2008年01期

6 林浩;皮军德;;有向网络上单源多汇的最优连接问题[J];系统工程学报;2008年01期

7 王素欣;高利;崔小光;陈雪梅;;多集散点车辆路径问题及其蚁群算法研究[J];系统工程理论与实践;2008年02期

8 韩丽霞;王宇平;;解旅行商问题的一个新的遗传算法[J];系统工程理论与实践;2007年12期

9 刘桂枝;高太平;;带二次参数赋权的多阶段网络最短路算法[J];系统工程理论与实践;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 张天澍;通过平面上几个定点的最短路[J];福州大学学报(自然科学版);1986年01期

7 李仁豪;;赋有权向量网络的2-范数意义下的最短路[J];山东矿业学院学报;1990年02期

8 郭强;;Hopfield神经网络结构在最短路问题中的应用[J];西安电子科技大学学报;1996年S1期

9 宋恩民,黄文奇,刘宏,李海山;含负权有向网络中最短路问题的求解算法[J];华中理工大学学报;1997年S1期

10 刘胤宏;含参数的最短路问题及其原始—对偶算法[J];湘潭师范学院学报(社会科学版);1999年06期

相关会议论文 前4条

1 袁二明;李莹;李彪;;基于交通拥堵预测的交通网络最短路问题的研究[A];“两型社会”建设与管理创新——第十五届中国管理科学学术年会论文集（上）[C];2013年

2 施欣;;随机运输网络最短路分布研究[A];复杂巨系统理论·方法·应用——中国系统工程学会第八届学术年会论文集[C];1994年

3 朱建明;沙丹;;时变网络中任意等待时间最短路问题的一个对偶算法(英文)[A];第四届中国智能计算大会论文集[C];2010年

4 牛宏睿;李平;史天运;;应急资源调度中最短路边权不确定性问题的建模与仿真[A];2009年中国智能自动化会议论文集（第七分册）[南京理工大学学报（增刊）][C];2009年

相关博士学位论文 前2条

1 吴六三;基于网络熵的网络可靠性研究[D];南京航空航天大学;2014年

2 高原;不确定图与不确定网络[D];清华大学;2013年

相关硕士学位论文 前9条

1 魏翔宇;面向最短路的网络阻断问题研究[D];国防科学技术大学;2014年

2 苏健;自动波方法求解TSP问题[D];西安电子科技大学;2004年

3 雷芬;随机网络中的动态最短路研究[D];中央民族大学;2009年

4 张振抻;网络最短路的解集结构及有关问题[D];郑州大学;2002年

5 张美玲;最短路问题的一个改进蚁群算法[D];兰州大学;2008年

6 陶娜娜;模糊随机多属性最短路问题[D];南京理工大学;2006年

7 台伟英;几类网络改进问题的算法及复杂性[D];中国计量学院;2012年

8 刘桂枝;带二次参数赋权多阶段网络的最短路问题研究[D];山西大学;2007年

9 张建勇;网络的K最短路分析与应用[D];山东科技大学;2006年

，

本文编号：2339757