コンピュータネットワークの最短経路アルゴリズムとは？代表的な3手法を徹底解説

コンピュータネットワークにおける最短経路アルゴリズムは、ルーティングコストを最小化するために、ネットワークノード間の最適な経路を求めることを目的とした手法です。グラフ理論で提唱された最短経路問題の解法を、ネットワークのルーティングに直接応用したものといえます。

基本概念

ネットワークを、N個の頂点（ノードまたはネットワーク機器）がM本の辺（伝送路）で接続されたグラフとして考えてみましょう。各辺には重みが割り当てられており、これは伝送路の物理的な距離や伝送遅延を表します。

最短経路アルゴリズムの目標は、任意の2つの頂点を結ぶ経路の中で、辺の重みの合計が最小になるものを見つけることです。すべての辺が同じ重みを持つ場合には、ホップ数（経由するリンク数）が最少となる経路を求めることになります。

代表的な最短経路アルゴリズム

• ベルマン・フォード法（Bellman-Ford Algorithm）
• ダイクストラ法（Dijkstra's Algorithm）
• ワーシャル・フロイド法（Floyd-Warshall Algorithm）

以降のセクションで、それぞれのアルゴリズムの仕組みを詳しく見ていきます。

ベルマン・フォード法（Bellman-Ford Algorithm）

入力：ネットワークを表すグラフと始点ノード s
出力：sから他のすべてのノードへの最短経路

• sから全ノードへの距離を無限大（∞）で初期化し、自分自身への距離のみ0に設定します。具体的には、ノード数 |V| のサイズを持つ配列 dist[] を用意し、dist[s] 以外をすべて ∞ とします。
• 反復計算によって最短距離を段階的に求めます。s以外の各ノードに対して |V| − 1回 繰り返します。
  • 頂点 u と v を結ぶ各辺について、以下の処理を行います。
    • dist[v] ＞ dist[u] ＋ 辺u-vの重み が成り立つ場合、
      dist[v] = dist[u] ＋ 辺u-vの重み に更新します。
• 処理終了後、配列 dist[] には s から各ノードへの最短経路のコストが格納されています。

ダイクストラ法（Dijkstra's Algorithm）

入力：ネットワークを表すグラフと始点ノード s
出力：s を根（ルート）とする最短経路木（SPT）

初期化

• ノード数 |V| のサイズを持つ距離配列 dist[] を用意します。dist[s] = 0 とし、それ以外のノード u については dist[u] = ∞（無限大）に設定します。
• グラフ内の全ノードを含む配列 Q を用意します。アルゴリズム完了時には Q は空になります。
• 訪問済みノードを登録するための空の集合 S を用意します。アルゴリズム完了時には、S にグラフ内の全ノードが含まれます。

処理手順

• Q が空になるまで、以下を繰り返します。
  • Q から、dist[u] が最小かつ S に含まれていないノード u を取り出します。最初の実行では、dist[s] が最小となるため s が選択されます。
  • u を S に追加し、訪問済みとしてマークします。
  • u に隣接する各ノード v について、dist[v] を以下の手順で更新します。
    • dist[u] ＋ 辺u-vの重み ＜ dist[v] が成り立つ場合、
      dist[v] = dist[u] ＋ 辺u-vの重み に更新します。
• 処理終了後、配列 dist[] には s から他のすべてのノードへの最短経路が格納されています。

ワーシャル・フロイド法（Floyd-Warshall Algorithm）

入力：ネットワーク内のノード間の経路を表すコスト隣接行列 adj[][]
出力：グラフ内の全ノードペア間の最小コストを示す最短経路コスト行列 cost[][]

• cost[][] を次のように初期化します。
  • adj[][] が空（経路が存在しない）の場合 → cost[][] = ∞（無限大）
  • それ以外の場合 → cost[][] = adj[][]
• N = |V| とします（V はネットワーク内のノード集合）。
• k = 1 から N まで繰り返します。
  • i = 1 から N まで繰り返します。
    • j = 1 から N まで繰り返します。
      • cost[i][k] ＋ cost[k][j] ＜ cost[i][j] が成り立つ場合、
        cost[i][j] := cost[i][k] ＋ cost[k][j] に更新します。
• 処理終了後、行列 cost[][] には、各ノード i から他のすべてのノード j への最短コストが格納されています。

3つのアルゴリズムの比較まとめ

まとめ

最短経路アルゴリズムは、コンピュータネットワークの効率的なパケット転送を支える基盤技術です。ベルマン・フォード法は負のコストにも対応できる柔軟性を持ち、ダイクストラ法は高速性から多くのルーティングプロトコルで採用され、ワーシャル・フロイド法は全ノード間の最短経路を一度に求められる点が特徴です。それぞれの特性を理解し、目的に応じて使い分けることが重要です。