私は次のような問題を与えられました：
整数の重み (正と負の両方) を持つ連結有向グラフが与えられた場合、2 つの頂点間の最短経路を見つけるアルゴリズムを開発します。
kruskal のような最小スパニング ツリー アルゴリズムを使用してから、ダイクストラのアルゴリズムを使用して、MST ではすべての頂点に入力エッジが 1 つしかないため、ダイクストラのアルゴリズムは負の重みでも機能することを示すことができると考えました。
これはコパスティックに聞こえますか？
PSすべての頂点について、有向グラフの最短パスがMSTに含まれていることを証明するのに苦労しています。
まず、グラフに負のサイクルがあってはならないことに注意してください。
第二に、通常、Dikstra は負の重みを持つグラフでは機能しません。
のどが渇いて、ベルマン・フォード・アルゴリズムを使用して、負の重みを持つ有向グラフで最短経路を見つけることができます。
すべての頂点について、有向グラフの最短パスが MST に含まれていることを証明するのに苦労しています。
それは嘘だからです。辺の重みが 2、3、4 の三角グラフを考えてみましょう。MST には重み 2 と 3 の辺しか含まれていませんが、最短経路の重みは 4 で、MST を通る経路の重みは 5 です。
このことを考えると、アルゴリズムに最小スパニング ツリーを埋め込むことは悪い考えのように思えます。