私が受講したプログラミングの授業では、Bellman-Ford SSSP と Djikstra の SSSP を学び、Bellman-Ford は Kruskal の最小スパニング ツリー アルゴリズムに基づいており、Djikstra のアルゴリズムは Prim の最小スパニング ツリー アルゴリズムに基づいていることを学びました。
すでに選択されているエッジとノードに基づいて比較を行うため、Djikstra と Prim は両方ともローカル レベルで動作することを覚えておくように言われましたが、これは理にかなっています。また、Bellman-Ford と Kruskal は、以前に選択したノードに関係なく最小のエッジ ウェイトを選択するため、グローバル レベルで動作したことを覚えておくように言われました。
Kruskal のアルゴリズムの場合、これがグローバルであると見なされる理由は理解できます。文字通り、最も軽いまたは最小のエッジの重みを選択するだけだからです。しかし、Bellman-Ford のアルゴリズムについては、以前に選択したノードとエッジについて心配する必要があるため、グローバルであると見なされる方法がわかりません。Bellman-Ford は、いったいどのように Kruskal のアルゴリズムに基づいているのでしょうか。