2

在我参加的编程课上，我们学习了 Bellman-Ford SSSP 和 Djikstra 的 SSSP，我们了解到 Bellman-Ford 是基于 Kruskal 的最小生成树算法，而 Djikstra 是基于 Prim 的最小生成树算法。

我们被告知要记住 Djikstra 和 Prim 都在本地级别上运行，因为您根据已经选择的边和节点进行比较，这对我来说很有意义。我们还被告知要记住 Bellman-Ford 和 Kruskal 在全局级别上运行，因为您选择最小的边权重，而不管之前选择的节点如何。

对于 Kruskal 的算法，我可以理解为什么我们可以认为这是全局的，因为您实际上只是选择最轻或最小的边缘权重。但是对于 Bellman-Ford 的算法，我只是不明白它是如何被认为是全局的，因为您仍然需要担心之前选择的节点和边。Bellman-Ford 到底是如何基于 Kruskal 算法的，它是如何被认为是“全球”运作的？

4

1 回答 1

1

将 Bellman-Ford 称为全局似乎是公平的，因为它由许多 (|V|-1) 个松弛通道组成，每个松弛通道都涉及迭代所有边并（可能）更新到（可能）每个其他顶点的距离估计。

我认为克鲁斯卡尔和贝尔曼福特之间没有任何明显的概念联系。事实上，我认为可以公平地说 Bellman-Ford 与 Dijkstra 更相似，因为它使用了迭代松弛。

于 2015-05-11T20:07:38.007 回答