ダイクストラとポテンシャルのはなし

はじめまして, niuezといいます. 競プロを少ししています.

最近勉強したことのメモ書きをしておきます.

ダイクストラ法

ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです.

具体的には

距離が未確定の頂点の中で一番小さいものを選び, 距離を確定させる.
選んだ頂点から距離が未確定の頂点に伸びる辺で, 未確定な距離をより短いものに更新する.

を繰り返します. これを実装すると $O(N)$ですが, よく知られるダイクストラの計算量は $O((E+ V) \log E)$ です(heapとかを使う).

#include <set>
#include <queue>
#include <vector>

struct edge {
  int u,v;
  int dist;
};

std::vector<int> dijkstra(const std::vector<std::vector<edge>>& g, int s) {
  std::vector<int> dist(g.size(), 1e9);
  using node = std::pair<int,int>;
  std::priority_queue<node,std::vector<node>, std::greater<node>> Q;
  dist[s] = 0;
  Q.push(node(dist[s], s));

  while(!Q.empty()) {
    int v = Q.top().second;
    int d = Q.top().first;
    Q.pop();
    if(dist[v] < d) continue;
    for(const auto& e: g[v]) {
      if(dist[e.u] + e.dist < dist[e.v]) {
        dist[e.v] = dist[e.u] + e.dist;
        Q.push(node(dist[e.v], e.v));
      }
    }
  }

  return std::move(dist);
}

ベルマンフォード法

ベルマンフォード法(Bellman-Ford)は任意の長さのグラフで始点からの最短距離を求めるアルゴリズムです. 負の長さの閉路があるときはもちろん求められませんが, この記事では考えないことにします.

$O(VE)$ で直感的にもわかりやすいアルゴリズムですね.

#include <vector>

struct edge {
  int u,v;
  int dist;
};

std::vector<int> dijkstra(const std::vector<std::vector<edge>>& g, int s) {
  std::vector<int> dist(g.size(), 1e9);
  dist[s] = 0;

  for(int c = 0;c < g.size();c++) {
      for(int v = 0;v < g.size();g++) {
          if(dist[v] == (int)1e9) continue;
          for(const auto& e: g[v]) {
            if(dist[e.u] + e.dist < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.dist;
            }
          }
      }
  }

  return std::move(dist);
}

負の重みがあるときはベルマンフォード法しか無い?

ダイクストラ法のほうが定数倍が早かったりするので, できるだけベルマンフォード法よりはダイクストラ法を使いたいですよね?

一回だけ最短経路を求めるときはベルマンフォード法を使うしかありません.

複数回最短経路を求めるときはどうでしょうか?

実はこの場合, ベルマンフォード法を最初に一回だけしておくことで, 後の複数回はダイクストラ法を使うことが出来ます.

ダイクストラ法を使うとすると, 辺の長さをうまいことして正の長さにする必要があります.

最短経路とは??

始点を頂点 $s$ とした最短経路を数式に落とし込むと, こういう定義になります.

$d_s = 0$ とする.
すべての辺 $(i,j)$ において $d_i + dist(i,j) \ge d_j$ が成り立つときの, $d$ のそれぞれの取れる最大値.

これを頭に入れておくと次がわかります.

ポテンシャル

ここで天才をします. 先人は天才です.

ある$p_i$という値を用意して, 距離を $dist'(i,j) = dist(i,j) + p_i - p_j$ としたグラフを考えます.

長さ $dist'$ のグラフで, 頂点 $s$ を始点とした最短距離を計算して, ${d'}_i$ を求めたとしましょう.

${d'}_i + dist'(i, j) \ge {d'}_j$

${d'}_i + dist(i, j) + p_i - p_j \ge {d'}_j$

${d'}_i + p_i + dist(i, j) \ge {d'}_j + p_j$

よく見ると

$d_i = {d'}_i + p_i$

とすれば, $d_i$は最短距離の定義を満たしているように見えますね.しかし

$d_s = {d'}_s + p_s = p_s`$

なので
$d_s = 0$ を満たしていません.
なので, すべての頂点 $i$ について $ans_i = {d'}_i + p_i - p_s$ を計算すれば, $ans$ は最短経路を示しています.

このとき, $p_i$ のことをポテンシャルと呼びます.

では, $dist'$を正の長さにしたい気持ちになります.

$dist(i, j) + p_i - p_j \ge 0$

$p_i + dist(i, j) \ge p_j$

これは何かな. 最短距離の定義そのままですね(天才).

これを使うと色々なものが効率的に求めることが出来ます.

負の重みがあるグラフでの全点間最短距離問題

全点間最短距離問題とは, すべての頂点の間での最短距離を計算する問題のことです.

よく知られているのはワーシャルフロイド法の $O(V³)$ ですが, これを $V$ 回のダイクストラに置き換えることが出来て, $O(V(E + V) \log V)$ になります.

疑似コード

proc all_pair_shortest_path(G, dist)
    let potential = bellman_ford(G, dist, 0) //引数は グラフ, 距離, 始点 です
    for e = (i, j) in G
        dist2(i, j) = dist(i, j) + potential[i] - potential[j]
    for s in [0, |V| - 1]
        result[s] = dijkstra(G, dist2, s)
        for j in [0, |V| - 1]
            result[s][j] += potential[j] - potential[s] // result[s][j]... s -> jの距離
    return result