コンピュータネットワークの最短経路アルゴリズム

コンピュータネットワークでは、最短経路アルゴリズムは、ルーティングコストを最小限に抑えるために、ネットワークノード間の最適な経路を見つけることを目的としています。これらは、グラフ理論で提案されている最短経路アルゴリズムの直接的なアプリケーションです。

説明

ネットワークは、M個のエッジ（伝送ライン）で接続されたN個の頂点（ノードまたはネットワークデバイス）で構成されていると考えてください。各エッジは、伝送線路の物理的な距離または伝送遅延を表す重みに関連付けられています。最短経路アルゴリズムのターゲットは、エッジに沿った頂点の任意のペア間のルートを見つけることです。そのため、エッジの重みの合計は最小になります。エッジの重みが等しい場合、最短経路アルゴリズムは、ホップ数が最小のルートを見つけることを目的としています。

一般的な最短経路アルゴリズム

一般的な最短経路アルゴリズムは次のとおりです-

• ベルマンフォードのアルゴリズム

• ダイクストラのアルゴリズム

• フロイドウォーシャルのアルゴリズム

次のセクションでは、これらの各アルゴリズムについて説明します。

ベルマンフォードアルゴリズム

入力-ネットワークを表すグラフ。およびソースノード、s

出力-sから他のすべてのノードへの最短経路。

• sからすべてのノードまでの距離を無限大（∞）として初期化します。それ自体までの距離は0です。配列dist[] サイズの|V | （ノードの数） dist [s]を除くすべての値が∞ 。

• 最短距離を繰り返し計算します。 | V |-1を繰り返します s-

  を除く各ノードの時間

  • 頂点uとvを接続するエッジごとに繰り返します-

    • dist [v]の場合> （dist [u] +エッジの重みu-v） 、次に

      • dist [v] =dist[u]+エッジの重みu-vを更新します

• 配列dist[] sから他のすべてのノードへの最短経路が含まれています。

ダイクストラのアルゴリズム

入力-ネットワークを表すグラフ。およびソースノード、s

出力-ルートノードとしてsを使用した最短パスツリーspt[]。

初期化-

• 距離の配列dist[] サイズの|V | （ノードの数）、ここで dist [s] =0 およびdist[u] =∞（無限）。ここで、uはsを除くグラフ内のノードを表します。

• 配列、 Q 、グラフ内のすべてのノードを含みます。アルゴリズムが完了すると、 Q 空になります。

• 空のセット、 S 、訪問先ノードが追加されます。アルゴリズムが完了すると、 S グラフ内のすべてのノードが含まれます。

• Qの間繰り返します 空ではない-

  • Qから削除します 、ノード、 u 最小の距離[u] Sにはありません 。最初の実行では、dist[s]が削除されます。

  • uを追加します S 、uを訪問済みとしてマークします。

  • ノードごとにv uに隣接しています 、 dist [v]を更新します として-

    • （dist [u] +エッジの重みu-v）の場合 < dist [v] 、次に

      • dist [v] =dist[u]+エッジの重みu-vを更新します

• 配列dist[] sからの最短経路が含まれています 他のすべてのノードに。

フロイドウォーシャルアルゴリズム

入力-コスト隣接行列、 adj [] [] 、ネットワーク内のノード間のパスを表します。

出力-最短経路コストマトリックス、コスト[] [] 、グラフ内のノードの各ペア間のコストの観点から最短経路を示しています。

• コスト[][]を入力します 次のように：

  • adj [] []の場合 空の場合コスト[][] =∞（無限）

  • それ以外の場合コスト[][] = adj [] []

• N = | V | 、ここで V ネットワーク内のノードのセットを表します。

• k=1からNまで繰り返します −

  • i=1からNまで繰り返します −

    • j=1からNまで繰り返します −

      • コスト[i][k]+コスト[k][j]の場合 <コスト[i][j] 、次に

        • コスト[i][j]を更新します ：=コスト[i][k]+コスト[k][j]

• マトリックスコスト[][] 各ノードからの最短コスト、 iが含まれます 、他のすべてのノードに対して、 j 。