c++ - Dijkstra または Bellman–Ford のアルゴリズムを使用した修正最短経路

Question

ダイクストラまたはベルマンフォードのアルゴリズムを使用して、特定の頂点に移動した場合にエッジの一部が影響を受けるグラフの最短経路を見つけるにはどうすればよいでしょうか。そのため、影響を受けるエッジの長さは、元の長さよりも長くなったり短くなったりします。

Answer 1

私がこれを正しく理解していれば、現在のパスで訪問されたノードに応じて、グラフ内のエッジのコストを変更したいと考えています。コメントの例は次のとおりです。

「エッジ AB の長さは 3 ですが、ノード C にもアクセスすると、AB の長さは 5 になります」

現在、Djikstraのアルゴリズムのようなものを使用する方法はないようです。そのアルゴリズムには、すべての段階で「最良の」ノードを選択する貪欲なステップがあるためです。その時点での「最良の」ノードが後で変更される可能性があるという考えは (上記のようなルールにより)、最善のコストから最悪のコストの順にノードを効果的に訪問していると仮定する貪欲なアプローチの概念に違反しています。これが提案されている NP ハードであるかどうかはわかりませんが、最初から Dijikstra のようなアプローチを使用することはできません。ただし、問題に対して+1。