O（E）最短経路

Question

O（E）で任意の重みを持つグラフ内の単一のソースから頂点までの最短経路を見つける方法はありますが、最短経路が7であれば心配する必要がありますエッジ以下である。

Bellman-Fordアルゴリズムの実行時間がO（E）の最善の場合は、ここで適用されますか？

Answer 1

あなたはすべての頂点へ< = N手順で最短経路を知っている場合、それはエッジを反復処理し、あなたは可能性が長いパスを評価することにより、< = N + 1手順で最短経路を計算するのは簡単ですそれぞれと一緒に作る。 N = 0で

は、ソース頂点までの最短経路の長さを有し、他のすべての頂点への最短経路（すなわち、あなたがそこに得ることができない）長さ無限を有します。あなただけが少しならO（E）の総走行時間のために、あなたは< = N = 7つのステップで取得することができますどこでもへの最短経路を見つけるためにエッジ回以上反復しなければなりませんデータ構造に注意してください。