CAJ | 학술논문

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