长话短说: 贝尔曼福特算法在加权有向图中找到单源最短路径，即使某些边具有负权重。将源距离初始化为零，将所有其他距离初始化为无穷大，将每条边放松到 V 负 1 倍，然后进行一次额外的传递：任何进一步的改进都证明存在可达到的负权重循环。
贝尔曼福特算法：编码面试指南
学习贝尔曼福特算法，跟踪边缘松弛，检测负循环，解释复杂性，并编写面试准备的伪代码。
试用 YesToTheOffer
什么是贝尔曼福特算法？
Bellman Ford 是一种动态编程式的最短路径算法。在第一次完整通过之后，最知名的路径最多使用一条边；在第二个之后，最多两个边缘。简单路径最多包含 V 减 1 条边，这解释了循环计数和正确性参数。与 Dijkstra 算法不同，贝尔曼·福特不假设非负边权重。
如何解释边缘松弛？
对于从 u 到 v 且权重为 w 的边，松弛会询问距离[u] + w 是否小于距离[v]。仅当 u 可达时才执行加法。如果候选者更好，则更新距离[v]并将前驱[v]设置为u。对于距离，前驱数组是可选的，但它可以让您重建实际路径并清楚地解释您的结果。
你如何在采访中追踪贝尔曼·福特？
使用一张小图并在每次通过时写出一个距离行。从源 A 的 0 处开始，每隔一个顶点在无穷远处。以一致的顺序扫描完整的边缘列表，记录每次更新。当整个通行证没有发生任何变化时，请尽早停止。明确的是，当不存在可到达的负循环时，边顺序可以改变中间行，但不能改变最终的正确距离。
你应该写什么伪代码？
创建距离和前驱数组，然后重复全边缘扫描 V - 1 次。使用更改的标志来提前终止。最后，再次扫描所有边缘，如果可达距离仍然可以改善，则报告负循环。在生产代码中，选择可以保存路径总和并在相加之前保护无穷大标记的数字类型。
时间和空间复杂度是多少？
标准邻接边列表实现的运行时间为 O(VE)，因为它可以在每个 V 减去 1 遍上扫描 E 边，再加上一次检测遍。它使用 O(V) 辅助空间来表示距离和前驱。提前停止可以改善有利的输入，但最坏情况的界限仍然是 O(VE)。
| 面试决定 | 使用贝尔曼福特时 | 当以下情况时更喜欢另一种方法 |
|---|---|---|
| 边权重 | 可能会出现负边沿 | 所有边都是非负的，速度很重要 |
| 周期要求 | 检测可到达的负循环 | 不需要循环检测 |
| 复杂 | O(VE) 可以接受 | 图形太大或太密集，无法重复扫描 |
您什么时候应该选择 Bellman Ford 而不是 Dijkstra？
当允许负边权重或面试官明确要求可达到的负循环检测时，选择贝尔曼·福特。对于边权重均为非负的图，选择带有优先级队列的 Dijkstra，因为它通常更快。对于全对最短路径，首先澄清图密度、负权重以及是否需要路径或仅需要距离。
你应该避免哪些错误？
不要从不可到达的顶点放松，不要将负边与负循环混淆，或者声称每个负循环都会使结果无效：只有从源可达的循环才会影响其最短路径。还要避免仅运行 V 减去 2 遍、跳过最终检测遍或在不维护前趋的情况下重建路径。
你如何练习解释？
练习三个版本：30 秒的定义、2 分钟的正确性解释和完整的实现。测试不可到达的顶点、没有循环的负边、可到达的负循环以及早期稳定的图。这将记忆的代码与真正的理解分开了。
使用人工智能来组织您已经理解的材料、排练解释并检查您的表现。遵循雇主和评估提供商的规则，切勿捏造经验、数字或结果。
继续阅读AI 面试副驾驶指南、简历基础准备 和面试后审核工作流程。
常见问题
FAQ
贝尔曼·福特可以处理负重吗？
是的。它可以处理负边权重。它无法为受可达负权重循环影响的顶点生成有限的最短路径，这就是为什么额外的松弛过程至关重要。
为什么贝尔曼·福特运行 V 负 1 次？
任何简单路径最多有 V 减 1 条边。在第 k 遍之后，算法考虑了最多使用 k 个边的最短路径，因此 V 减 1 遍覆盖了每个简单的最短路径。
贝尔曼·福特如何检测负循环？
正常通过后，再次扫描每个边缘。如果可达距离仍然可以减少，则存在可达负权循环，因为一条简单路径应该已经最终确定。
贝尔曼·福特的复杂性是什么？
标准算法使用 O(VE) 时间和 O(V) 辅助空间。当完整传递没有更新时，提前退出标志可以停止循环，但它不会改变最坏情况的界限。
贝尔曼·福特比迪杰斯特拉好吗？
两者都不是普遍更好。 Bellman Ford支持负权重和循环检测；当所有边权重均为非负时，Dijkstra 通常会更快。
用证据而不是剧本来练习
YesToTheOffer 可以在您的简历、角色描述和私人笔记中进行基础准备和实时答案结构，然后保存笔录以供面试后审核。
用证据而不是剧本来练习
YesToTheOffer 可以在您的简历、角色描述和私人笔记中进行基础准备和实时答案结构，然后保存笔录以供面试后审核。
试用 YesToTheOffer