使用Bellman-Ford算法的简单图遍历[关闭]

Question

我有点卡住了 我们应该在基本有向图上运行Bellman-Ford算法的两次迭代后填充值的问题。

我相信我理解第一次迭代，并且我理解“松弛边缘权重”的概念，因为找到了较短的路径。但是，我没有看到在这个特定问题中，第二次迭代如何产生比第一次迭代中的路径更短的路径。

例如，我知道通过从节点A开始的路径访问节点'C'，然后转到节点'B'然后转到节点'C'将具有6 + 8 = 14的总“成本”。但是，因为该图的遍历顺序是：AB，AC，BC，BD等，通过节点B（14）到达节点C的成本永远不会被保存，因为已经找到了直接从A到C的较短路径（产生7的成本）我没有看到任何额外的迭代如何给出从A到C的较短路径长度，例如这似乎是后续迭代的重要性。

Answer 1

经过仔细检查，似乎数据确实是正确的。这只是一个格式不正确的问题，在这个特殊情况下，第二次迭代不会产生边缘的任何进一步“松弛”，因此误导那些期望在第二次迭代中看到差异的人。