本文从零开始介绍 Bellman-Ford。重点不是背诵代码，而是理解它解决什么问题、为什么有效、如何实现，以及它在真实软件系统中的使用场景。
它解决什么问题？
本文从零开始介绍 Bellman-Ford。重点不是背诵代码，而是理解它解决什么问题、为什么有效、如何实现，以及它在真实软件系统中的使用场景。
最简单的核心思想
先把问题表示成图，再按照明确规则处理节点和边，直到得到目标结构或答案。
逐步执行过程
- 明确业务问题中的节点和边分别代表什么。
- 选择合适的图存储方式。
- 维护 visited、distance、degree 等必要状态。
- 在实际使用前验证结果和边界情况。
JavaScript 示例
JavaScript
function bellmanFord(vertices, edges, source) {
const dist = Object.fromEntries(vertices.map(v => [v, Infinity]));
dist[source] = 0;
for (let i = 0; i < vertices.length - 1; i++)
for (const [u,v,w] of edges)
if (dist[u] !== Infinity && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
for (const [u,v,w] of edges)
if (dist[u] !== Infinity && dist[u] + w < dist[v])
throw new Error("Negative cycle");
return dist;
}真实世界与工作场景
- 用户与服务之间的关系分析
- 软件模块依赖管理
- 网络与通信
- 业务系统中的路径与工作流
时间与空间复杂度
O(VE) زمان و O(V) حافظه
什么时候使用？
当问题结构和目标与该算法针对的问题类型一致时使用。
什么时候不适合？
如果图的类型或目标不同，不要机械套用；其他算法可能更简单或更快。
总结
不要只根据算法名称做选择。先明确图是有向还是无向、加权还是无权，以及目标究竟是遍历、可达性、最短路、连通性、生成结构还是组合优化。