加重グラフ G を取り、G の最小スパニング ツリーの変化を引き起こす非 MST エッジへのコストの最小の変化を見つけるアルゴリズムを考案します。
これまでの私の解決策（提案が必要）：
MST に変更を加えるには、非 MST エッジ st の重みを変更する必要があります。これは、MST の開始頂点と終了頂点のパスの最大エッジよりも 1 小さくなります。
したがって、MST のエッジをウォークすることから始めて、頂点ごとに非 MST エッジがあるかどうかを確認します。存在する場合、(MST 内の) エッジの終点に到達するための bfs を実行できます。非 MST エッジの重みは、パス内の最大エッジの重みよりも 1 小さい値に更新する必要があります。
これにより、非 MST エッジが MST に含まれ、以前の最大エッジが MST から削除されます。
この解決策が正しいかどうか誰かがわかりますか? ありがとう。