無向加重グラフG、および2つの頂点が与えられた場合：開始頂点と終了頂点
正確に1つのエッジの重みをゼロに変える機能を備えた、最初から最後までの最短経路を見つける最も効率的なアルゴリズムは何ですか？
編集：私はダイクストラアルゴリズムを知っていますが、私が言ったように、この問題では状況が異なります：1つのエッジをゼロに変えることができます、
この問題を効率的に解決する方法を知りたいのですが、実際には、エッジの重みを繰り返しゼロにする方法があります。各ステップでダイクストラアルゴリズムを適用しますが、より効率的な方法を探しています
ありがとう
これは、2倍のサイズの拡張グラフでダイクストラのアルゴリズムを使用することで解決できます。
頂点が1...nであるとします。
元のエッジa->bの重みがwで、エッジa-> bの重みがw、a-> b + nの重みが0、a + n-> b+nのエッジが0になるように新しいグラフを定義します。重量w。
頂点n+1..n + nは、元のグラフのコピーを含む複製であるという考え方です。元のグラフから複製に移動することは、エッジを0に変える特殊な機能を使用することを表します。複製に入ると、元のグラフに戻る方法がないため、この特殊な機能は1回しか使用できないことに注意してください。
したがって、最初から最後まで+ nの拡張グラフで問題を解決して、単一の重みを0に設定する機能を含む最短経路を見つける必要があります。
ダイクストラのアルゴリズム は、これらのタイプの問題を解決するために一般的に使用されます。また、これはTSP問題のように聞こえますが、その部分は間違っている可能性があります。