快速负环检测的负权最短路径算法

摘要：

为优化存在负环的有向图[1]中的单源最短路径问题，针对有向图中的负环检测，提出一种基于快速检测负环的最短路径算法。采用最短路径树的数据结构，在时间复杂度O （n2）内，检测出负环，如果不存在负环，就将获得源节点到其它节点的最短路径距离。实验结果表明，与现有的方法相比，该算法在负环检测方面具有明显优势。

关键词：最短路径树、负环、快速检测、Bellman-Ford算法、有向图

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目63179057

在线出版日期：2014-10-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：3455-3460