今天介绍一种计算单源最短路径的算法Bellman-Ford算法，对于图G=(V,E)来说，该算法的时间复杂度为O(VE)，其中V是顶点数，E是边数。Bellman-Ford算法适用于任何有向图，并能报告图中存在负环路（边的权重之和为负数的环路，这使得图中所有经过该环路的路径的长度都可以通过反复行走该环路而使路径长度变小，即没有最短路径）的情况。以后会介绍运行速度更快，但只适用于没有负权重边的图中的Dijkstra算法。Dijkstra算法可以参考我的下一篇博客今天介绍一种计算单源最短路径的算法Bellman-Ford算法，对于图G=(V,E)来说，该算
阅读背景：
单源最短路径之Bellman-Ford算法
来源：互联网
分享到：
