贝尔曼-福特算法 编辑
贝尔曼-福特算法，求解单源最短路径问题的一种算法，由理查德·贝尔曼 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行




|

V

|

−
1


{\displaystyle |V|-1}

次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达



O



{\displaystyle O}

。但算法可以进行若干种优化，提高了效率。
2
相关
距离向量路由协定，为路由协定中的两大分类之一，这类协定采用距离向量算法来决定封包交换的路径。包括贝尔曼-福特算法，Ford–Fulkerson algorithm与DUAL FSM等算法，都被归类于距离向量算法中。
距离向量路由协定，为路由协定中的两大分类之一，这类协定采用距离向量算法来决定封包交换的路径。包括贝尔曼-福特算法，Ford–Fulkerson algorithm与DUAL FSM等算法，都被归类于距离向量算法中。
最短路径快速算法，国际上一般认为是带有队列优化的贝尔曼-福特算法，一般仅在中国大陆被称为SPFA，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。 然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同，因此在非负边权的图中使用堆优化的戴克斯特拉算法效率可能优于SPFA。 SPFA算法首先在1959年由Edward F. Moore作为广度优先搜索的扩展发表，相同算法在1994年由段凡丁重新发现。
最短路径快速算法，国际上一般认为是带有队列优化的贝尔曼-福特算法，一般仅在中国大陆被称为SPFA，是一个用于求解有向带权图单源最短路径的算法。这一算法在随机的稀疏图上表现出色，并且适用于带有负边权的图。 然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同，因此在非负边权的图中使用堆优化的戴克斯特拉算法效率可能优于SPFA。 SPFA算法首先在1959年由Edward F. Moore作为广度优先搜索的扩展发表，相同算法在1994年由段凡丁重新发现。