単一始点最短路（Dijkstra法）

重みが全て\(0\)以上である任意の重み付きグラフ\(G\)における単一始点最短路は，Dijkstra法によって\(O(|E| \log |V|)\)で求めることができる．

単一始点最短路とは，あるノード\(s \in G\)から，\(G\)に含まれる任意のノードまでの最短路である．以降始点を\(s\)と呼ぶ．

説明

以下では，あるノード\(i\)について，\(s\)から\(i\)までの最短路長を\(d_{s→i}\)とする．また，あるノード\(i\)から出てあるノード\(j\)に入る(有向)辺の重みを\(e_{i→j}\)とする．

前提条件から全ての辺の重みが\(0\)以上であるため，\(s\)から到達可能な任意の\(y\)について以下の式が成り立つ．

$$d_{s→y} = min(d_{s→x} + e_{x→y}) \quad ただし \quad d_{s→x} \geq d_{s→y} \quad とする．$$

よって，\(d_{s→y}\)を小さい方から求めていくことで\(s\)を始点とする単一始点最短路を求めることができる．

単一終点最短路

\(G\)に含まれる辺の向きを全て逆向きにしたグラフを\(\hat{G}\)とし，\(i \in G\)に対応する\(\hat{G}\)のノードを\(\hat{i}\)と表す．

任意のノードについて\(s\)を終点とする最短路を求めるには，\(\hat{G}\)について\(\hat{s}\)を始点とした最短路を求めればよい．

説明

以下では，あるノード\(i\)について，\(i\)から\(s\)までの全経路の集合を\(P_{i→s}\)と表す．

任意のノード\(x \in G\)について，\(P_{x→s}\)の辺の向きを全て逆向きにした経路の集合は\(P_{\hat{s}→\hat{x}}\)と明らかに等しいため，\(s\)を終点とする最短路を求めることは\(\hat{s}\)を始点とする最短路を求めることと同義である．

実装

プライオリティキューを用いて，路長優先探索（造語）をすることで求められる．計算量は，取り出しに\(O(\log |V|)\)かかるキューを用いていることから，\(O(|E| \log |V|)\)となる．

コード

pair<vector<i64>, vector<int>> dijkstra(int s, i64 n, Graph &g) {
  vector<int> prev(n, -1);
  vector<i64> d(n, inf);
  d[s] = 0;
  priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> que;
  que.push({0, s});
  while (!que.empty()) {
    pair<i64, i64> p = que.top();que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (Edge &e: g[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        prev[e.to] = v;
        que.push({d[e.to], e.to});
      }
    }
  }
  return {d, prev};
}

// 経路復元
vector<pair<int, int>> get_path(int t, vector<int> &prev) {
  vector<pair<int, int>> path;
  for (; prev[t] != -1; t = prev[t]) path.push_back({prev[t], t});
  reverse(all(path));
  return move(path);
}