頂点が最短経路のいずれかにあるかどうかを決定するアルゴリズム

Question

正のエッジコストを持つ無向グラフG = {E、V}が与えられた場合。すべてのノードの組み合わせに対して、特定のノードvがエンドポイントではない最短パスのいずれにも存在しないかどうかを判断する方法はありますか？

私は、vが解決策に含まれていれば、v以外の各ノードでDijkstra's Algorithmの修正された形式を実行することでこれを実行できると考えました。しかし、私はこれを行うアルゴリズムを変更する方法がわかりません。

Answer 1

vが頂点であり、aとbが開始点と終了点であるとします。

1. aからbへの最短経路長を見つけます。
2. aからvとvからbへの最短経路長を見つけます。
3. ステップ2の合計がステップ1の値と等しい場合、vはaからbまでの潜在的な最短経路にあります。

PS：アルゴリズムの複雑さは、最短経路を見つけるのと同じです。

更新：Dijkstraは1つのノードから開始し、それから他のノードに最小距離を伝播します。それはすべてのノード（while Q is not empty）に到達するまでこれを行います。特定のノード（エンドポイント）に興味がある場合は、そのポイントに達するまでダイクストラでこのプロセスを実行できます（tがターゲットポイントであるとします）Qから抽出したuまでの距離伝播を行います。行u ← vertex in Q with min dist[u]u equals tあなたはreturn dist[u]することができます）。 Dijkstraと良いグラフィックスのイラストについては、thisをご覧ください。