期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

次短路问题算法综述

The algorithm of the next-to-shortest path problem
下载PDF
导出
摘要 最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者;给出已解决的次短路问题算法,列出尚未解决的次短路问题。 A shortest path is a path having the minimum length of all paths. A next-to-shortest path is a shortest path amongst all paths having length strictly greater than the length of a shortest path. The algorithm to solve the next-to-shortest path problem has been given, and the next-to-shortest path problem has not been solved yet.
作者 曾庆红 李祥
机构地区 保山学院数学学院
出处 《保山学院学报》 2016年第2期33-34,45,共3页 JOURNAL OF BAOSHAN UNIVERSITY
基金 云南省教育厅一般项目"次短路及第K短路问题的算法研究"(项目编号:2014Y485)
关键词 最短路 次短路 算法 shortest path next-to-shortest path algorithm
分类号 O13 [理学—基础数学]
  • 相关文献

参考文献9

  • 1曾庆红.无向图中严格第三短路问题的多项式时间算法[J].云南民族大学学报（自然科学版）,2014,23(1):58-61. 被引量：1
  • 2Lalgudi K N, Papaefthymiou M C. Computing strictly-second shortest paths[J]. Information processing letters, 1997,63(4).
  • 3Krasikov I, Noble S D. Finding next-to-shortest paths in a graph [J]. Information processing letters, 2004,92(3).
  • 4Li S, Sun G, Chen G. Improved algorithm for finding next-to-shortest paths[J]. Information processing letters, 2006,99(5).
  • 5Kao K H, Chang J M, Wang Y L, et al. A quadratic algorithm for finding next-to-shortest paths in graphs[J]. Algorithmica, 2011,61(2).
  • 6Wu,B.-Y.:A Simpler and More Efficient Algorithmfor the Next-to-Shortest Path Problem[J]. Algorithmica, 2011.
  • 7Zhang, C., Nagamochi, H.: A Polynomial-Time Al- gorithm for the Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights[J]. 2011.
  • 8Zeng Qinghong, Yang Qiaoyan. The polynomialtime algorithm of the next-to-shortest path problem in directed graph [J]. Social Science and Environment, 2016,1(23-24).
  • 9Tholey T. Linear time algorithms for two disjoint paths problems on directed acyclic graphs[J]. Theoreti- cal Computer Science, 2012,465.

二级参考文献9

  • 1LALGUDI K N,PAPAEFTHYMIOU M C. Computing strictly-second shortest paths[J].{H}Information Processing Letters,1997,(04):177-181.
  • 2KRASIKOV I,NOBLE S D. Finding next-to-shortest paths in a graph[J].{H}Information Processing Letters,2004,(03):117-119.doi:10.1016/j.ipl.2004.06.020.
  • 3LI S,SUN G,CHEN G. Improved algorithm for finding next-to-shortest paths[J].{H}Information Processing Letters,2006,(05):192-194.doi:10.1016/j.ipl.2006.04.013.
  • 4KAO K H,CHANG J M,WANG Y L. A quadratic algorithm for finding next-to-shortest paths in graphs[J].{H}ALGORITHMICA,2011,(02):402-418.
  • 5WU B Y. A simpler and more efficient algorithm for the next-to-shortest path problem[A].Berlin Heidelberg:Springer,2010.219-227.
  • 6ZHANG C,NAGAMOCHI H. The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights[A].2012.13-20.
  • 7WU B Y,GUO J L,WANG Y L. A linear time algorithm for the next-to-shortest path problem on undirected graphs with nonnegative edge lengths[J].arXi preprint arXiv:1203 5235,2012.
  • 8YEN J Y. Finding the k shortest loopless paths in a network[J].{H}Management Science,1971,(11):712-716.
  • 9KATOH N,IBARAKI T,MINE H. An efficient algorithm for k shortest simple paths[J].{H}NETWORKS,1982,(04):411-427.
保山学院学报
2016年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部