DijkstraまたはBellman – Pordのアルゴリズムを使用した最短パスを修正した

Question

DijkstraまたはBellman -Pordのアルゴリズムを使用して、特定の頂点に移動するとエッジの一部が影響を受けるグラフで最短パスを見つけるにはどうすればよいですか。そのため、罹患したエッジの長さは、元の長さよりもまたはそれほど小さいものになります。

Answer 1

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

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

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