MST に新しい頂点を追加して MST を更新しようとしています。このために、私は Chin と Houck による「スパニング ツリーの更新」に従っています。 http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf
論文のステップでは、2 つの特定の頂点間のパスで最大のエッジを見つける必要があります。私の考えは、頂点間のすべての可能なパスを見つけてから、パスから最大のエッジを見つけることです。これをMATLABに実装しようとしています。しかし、これまでのところ、私は成功していません。2 つの頂点間のすべてのパス、または 2 つの指定されたノード/頂点間のパスの最大のエッジさえも見つけるリード/クリア アルゴリズムは大歓迎です。
参考までに、例を挙げたいと思います。グラフに次のエッジ 1-2、1-3、2-4、および 3-4 がある場合、4 と 4 の間のパスは次のようになります。
1) 4-2-1-3-4
2) 4-3-1-2-4
ありがとうございました
このアルゴリズムは、t値を下げて、新しいMSTから大きなエッジを除外することで機能します。アルゴリズムが完了すると、tはMSTを完了するために挿入される残りの最低エッジになります。
m値は、INSERTの各実行に対してローカルな、rからzへのパス上の最大のエッジを表します。可能であれば、ループの各反復でmが下げられ、それによってtの候補として前のmエッジが削除されます。
言葉で説明するのは簡単ではありません。手順が明確になるまで、紙でアルゴリズムを実行することをお勧めします。
ここで手順を簡単にスケッチしようとしました：http：//jacob.midtgaard-olesen.dk/ ？p = 140
ただし、基本的に、アルゴリズムは、新しいノードzと古いMSTの別のノードの間に追加する小さなエッジが見つからない限り、古いMSTからエッジを追加します。この例では、アルゴリズムによってBへのより良い接続が見つかったため、エッジ（A、B）は新しいツリーにありません。
hとkを選択する際に、tと（w、r）のエッジ値が等しい場合は、（w、r）を選択する必要があることに注意してください。
最後に、アルゴリズムが機能する理由を理解するために、アルゴリズムに従って証明をたどる必要があります。（私はそれをすべて読んだわけではありません:)）