在我参加的一个编程课程中，我们学习了Bellman Ford的SSSP和Djikstra的SSSP，我们学习了Bellman Ford基于Kruskal的最小生成树算法，Djikstra基于Prim的最小生成树算法。
我们被告知要记住，djikstra和prim都是在本地操作的，因为您是根据已经选择的边和节点进行比较的，这对我来说很有意义。我们还被告知要记住，bellman ford和kruskal是在全局级别上操作的，因为您选择最小的边权重，而不考虑以前选择的节点。
对于kruskal的算法，我可以理解为什么我们可以将其视为全局的，因为实际上您只需选择最轻或最小的边权重。但是对于bellman-ford的算法，我只是不理解它是如何被视为全局的，因为您仍然需要担心以前选择的节点和边。贝尔曼福特是如何基于克鲁斯卡尔的算法的？它是如何被认为是“全球”运作的？
最佳答案
这似乎是公平的称为贝尔曼福特全球，因为它包括许多（| V |-1）松弛过程，每一个涉及迭代所有边缘和更新距离估计（潜在地）每一个其他顶点。
我认为克鲁斯卡尔和贝尔曼福特之间没有任何明显的概念联系事实上，我认为可以公平地说，贝尔曼福特更类似于dijkstra，因为它使用迭代松弛。
关于algorithm - Bellman-Ford SSSP如何“全局”运营？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30175046/