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