テクノロジー編26: アルゴリズム

グラフ上の 2 点間の最短経路を求める問題。
場合によっては最短距離だけを求めることもある。
たとえば地図アプリやネットワークのルーティングなどで使用されている。

BFS も最短経路探索のアルゴリズムの 1 つだが、ノード間の距離がすべて等しい場合にのみ利用できる。

エドガー・ダイクストラにより提案。
すべてのノード間の距離が非負であることが前提。
時間計算量は O(n^2) や O((n + m) log n) など。

1. 開始ノードを設定し、距離を 0 で初期化する。 他のノードの距離を無限大で初期化する。
2. 未訪問のノードの中から、距離が最小のノードを選択する。
3. 選択したノードを訪問済みとしてマークする。
4. 選択したノードから隣接するノードについて、そのノードへの距離を計算する。 距離が現在求まっている距離よりも小さい場合は、隣接ノードの距離を更新する。
5. この操作を、距離が無限大でない未訪問のノードがなくなるまで繰り返す。

// ノードの数
int n = ...;
// グラフの隣接行列
// つまり、 graph[i][j] はノード i からノード j への距離
// もしノード i からノード j への距離が存在しない場合は、 Integer.MAX_VALUE を設定する
int[][] graph = ...;

// 最短距離を格納する配列
int[] dist = new int[n];
// 直前に訪問したノードを格納する配列 (pre[i] = j ならば、ノード i の直前に訪問したノードは j)
int[] pre = new int[n];

// 開始地点
int start = 0;
// 初期化
for (int i = 0; i < n; i++) {
    dist[i] = Integer.MAX_VALUE; // 無限大で初期化
    pre[i] = -1; // 直前のノードは未設定
}
dist[start] = 0; // 開始地点の距離は 0

// 処理
for (int _ = 0; _ < n - 1; _++) {  // n - 1 回繰り返せば十分
  // 未訪問のノードから最小距離のノードを選択
  int u = -1;
  for (int i = 0; i < n; i++) {
    if (dist[i] != Integer.MAX_VALUE && (u == -1 || dist[i] < dist[u])) {
      u = i; // 最小距離のノードを更新
    }
  }
  // 距離を更新する
  for (int i = 0; i < n; i++) {
    if (graph[u][i] != Integer.MAX_VALUE) { // 隣接ノードが存在する場合
      int newDist = dist[u] + graph[u][i];
      if (newDist < dist[i]) { // 新しい距離が小さい場合
        dist[i] = newDist; // 距離を更新
        pre[i] = u; // 直前のノードを更新
      }
    }
  }
}

// 結果の表示
for (int i = 0; i < n; i++) {
  if (dist[i] == Integer.MAX_VALUE) {
    System.out.println("ノード " + i + " への到達不可");
  } else {
    System.out.println("ノード " + i + " までの最短距離: " + dist[i]);
    // 最短経路を表示
    System.out.print("最短経路の逆順: ");
    int current = i;
    while (current != -1) {
      System.out.print(current + " ");
      current = pre[current];
    }
    System.out.println();
  }
}

負の距離を持つグラフでも正しく動作する最短経路探索アルゴリズム。
リチャード・ベルマンとレスター・フォード・ジュニアによって提案された。
負の閉路を検出することもできる。
時間計算量は O(nm)。

1. 開始ノードを設定し、距離を 0 で初期化。 他のノードの距離を無限大で初期化。
2. すべての辺 (u, v) に対して、もし dist[u] + weight(u, v) < dist[v] ならば、dist[v] を更新。
3. この操作を、 n - 1 回繰り返す。
4. もう一度 2 の操作をおこない、もし dist[v] が更新されるノードがあれば、負の閉路が存在する。

// ノードの数
int n = ...;
// 辺の数
int m = ...;
// グラフの辺のリスト
// つまり、 edges[i] = (u, v, w) はノード u からノード v への距離が w の辺
int[][] edges = ...;
// 最短距離を格納する配列
int[] dist = new int[n];
// 直前に訪問したノードを格納する配列 (pre[i] = j ならば、ノード i の直前に訪問したノードは j)
int[] pre = new int[n];

// 開始地点
int start = 0;
// 初期化
for (int i = 0; i < n; i++) {
    dist[i] = Integer.MAX_VALUE; // 無限大で初期化
}
dist[start] = 0; // 開始地点の距離は 0

// 処理
for (int iter = 0; iter < n; iter++) { // n 回繰り返す
  for (int i = 0; i < m; i++) { // すべての辺を確認
    int u = edges[i][0]; // 辺の始点
    int v = edges[i][1]; // 辺の終点
    int w = edges[i][2]; // 辺の重み
    if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) { // 更新可能な場合
      dist[v] = dist[u] + w; // 距離を更新
      pre[v] = u; // 直前のノードを更新

      // もし n 回目の繰り返しで更新があった場合、負の閉路が存在する
      if (iter == n - 1) {
        System.out.println("負の閉路が存在します。");
        return;
      }
    }
  }
}