处理负权图最短路及判定负环之Dijkstra算法的改进

作者：李宇鹏

来源：中国新通信, 2019, 21(07): 166-167.

• 最短路径
• Dijkstra算法
• 负权图

最短路径搜索算法主要包括Floyd,Bellman-Ford及其优化SPFA,还有Dijkstra三种。本文简要分析了三种算法的框架及性能,根据发现的负权图处理问题,选择Dijkstra算法对处理负权图及判断负环给出进一步地说明与研究,讨论出新的算法并用实验验证了其正确性。