贝尔曼-福特SSSP是如何“全球”运作的？

Question

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

我们被告知要记住，贾克斯特拉和普里姆都是在地方层面上操作的，因为你根据已经选择的边缘和节点来进行比较，这对我来说是有意义的。我们还被告知要记住，Bellman和Kruskal在全球范围内运作，因为您选择最小的边缘权重，而不考虑先前选择的节点。

对于Kruskal的算法，我能理解为什么我们可以认为这是全局的，因为你实际上只是选择最轻或最小的边缘重量。但是对于Bellman的算法，我只是不明白它是如何被认为是全局的，因为您仍然需要担心先前选择的节点和边缘。在世界上，Bellman是如何根据Kruskal的算法建立的，它是如何被认为是“全球的”运作的？

Answer 1

把Bellman称为全局似乎是公平的，因为它包含了许多松弛传递，其中每一个都需要遍历所有的边，并将距离估计更新到(潜在的)其他每个顶点。

我不认为Kruskal和Bellman之间有任何明显的概念联系。事实上，我认为公平地说，由于使用迭代放松，Bellman与Dijkstra更相似。