Bellman-Ford

释义 Definition

Bellman-Ford（贝尔曼-福特算法）：一种用于在带权有向图中求单源最短路径的算法，特点是能够处理负权边，并可检测图中是否存在负权环（若存在，则最短路径无定义）。

发音 Pronunciation (IPA)

/ˈbɛlmən fɔːrd/

例句 Examples

The Bellman-Ford algorithm can handle negative edge weights.
Bellman-Ford 算法可以处理带负权的边。

If Bellman-Ford still relaxes an edge after (V-1) iterations, it indicates a reachable negative cycle in the graph.
如果在进行 (V-1) 轮松弛之后 Bellman-Ford 仍能继续松弛某条边，就说明图中存在一个从起点可达的负权环。

词源 Etymology

该名称来自两位研究者的姓氏：Richard Bellman（理查德·贝尔曼）与Lester R. Ford Jr.（莱斯特·福特）。相关思想与“动态规划/最优性原理”以及早期的最短路研究密切相关，后被系统化为常用的最短路径算法之一。

相关词 Related Words

• Dijkstra
• Shortest-Path
• Graph
• Edge-Weight
• Negative-Cycle
• Relaxation
• Dynamic-Programming

文学与著作中的出现 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）中在“单源最短路径”章节系统介绍 Bellman-Ford 及其负环检测。
• Algorithms（Robert Sedgewick, Kevin Wayne）在图算法部分讨论最短路径问题并提及 Bellman-Ford 的适用场景。
• The Algorithm Design Manual（Steven S. Skiena）在图与最短路径相关章节中将 Bellman-Ford 作为处理负权边的经典方法之一。