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

摘要

为优化存在负环的有向图[1]中的单源最短路径问题，针对有向图中的负环检测，提出一种基于快速检测负环的最短路径算法。采用最短路径树的数据结构，在时间复杂度O （n2）内，检测出负环，如果不存在负环，就将获得源节点到其它节点的最短路径距离。实验结果表明，与现有的方法相比，该算法在负环检测方面具有明显优势。%To optimize the single source short path problem in the negative cyclic directed graphic [1]and aiming at the negative cy-cle detection ,a new algorithm based on quick negative cycle detection was presented with the data structure of the shortest path tree ,which detected negative cycle within the time complexity of O (n2) ,otherwise the shortest path from single source vertex to any other vertexes was gotten if no negative cycles existed .Experimental results show that compared with the existing methods ,the algorithm in detecting negative cycles has more advantages .