algorithm - 負のエッジがある無向グラフで最小重みスパニング ツリーを見つける

Question

だから私はこのグラフを解決する必要があります.私はそれを解決する方法について一般的な考えを持っていますが、これを間違っている場合は私を修正してください.

したがって、MST を見つけるには、グラフでクルスカルス アルゴリズムを実行する必要があります。

これが、このクルスカルス アルゴリズムの擬似コードです。

Kruskal(V,E) A = null; for each v が V に含まれる make disjoint set(v) E を重みで徐々にソート for each(v1, v2) が E に含まれる if

  クラスカル(V,E)


A = ヌル;
V に含まれる各 v について
     互いに素な集合を作る(v)
E を重みで並べ替える
for each(v1, v2) は E に含まれます
     Find(v1) が Find(v2) と等しくない場合
          A = A ユニオン {(v1,v2)}
          ユニオン(v1,v2)
リターンA

だから私が最初にすることは、最短距離のノードを見つけることですよね?

1)

d(h,s) = -3 であるため、S から H への距離が最短であると仮定します。

だから A = {(h,s)}

だから今、私たちはこのパターンに従います

2) A = {(h,s),(s,f)}

3) A = {(h,s),(s,f)(s,n)}

4) A = {(h,s)(s,f)(s,n)(f,k)}

5) A = {(h,s)(s,f)(s,n)(f,k)(s,m)} (h から n へのパスが既に作成されているため、H から N をスキップします。 s )

6) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)}

7) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)(b,m)}

では、すべてのエッジに接続するパスがあるので、これで問題ありません。

しかし、私が理解していないのは、複数の頂点を通るパス[u、v]よりも短い距離[u、v]があることです。たとえば、d[d,m] は、最初に B を通過する p[d,m] よりも短くなります。私は何か間違ったことをしていますか？