Contents

概要

ダイクストラ法は、単一始点最短経路問題のアルゴリズムの一つです。

基本的な考え方は貪欲法です。以上！

オーダーは実装方法によって異なり、挑戦数をV、辺の数をEとした時以下のようになります。

深さ優先探索を用いる場合：O(V^2)
priority_queueを用いる場合：O(E logV)

DFSだとスタックオーバーフローの可能性もあるので、以下ではpriority_queueの例を掲載します。

制約

コストが負の辺(正確には負の閉路)が存在する場合、このアルゴリズムは使用できないことに注意してください。
負辺を持つグラフの最短経路問題はベルマンフォード法を使用しましょう。

経路復元

探索中に経路を更新する際、その頂点にどの頂点から来たか、一個手前の頂点の情報を保存しておきます。
ゴール側からその情報を辿ることで経路を復元することができます。

ライブラリ

拡張ダイクストラを実装しやすくするために、priority_queueをtupleで実装しています。

// const long long INF = 1LL << 60;

template <typename T>
struct Edge {
  int to;
  T cost;
};

// Dijkstra
template <typename T>
class Dijkstra {
 private:
  vector<vector<Edge<T>>> G;
  int num_v;

 public:
  Dijkstra(int num_v) : G(num_v), num_v(num_v) {
  }

  void add_edge(int from, int to, T cost) {
    G[from].push_back((Edge<T>){to, cost});
  }

  // start: Start point
  // result: result
  void solve(int start, vector<T>& result) {
    vector<int> tmp;
    solve(start, result, tmp);
  }

  void solve(int start, vector<T>& result, vector<int>& prev) {
    result.resize(num_v);
    std::fill(result.begin(), result.end(), INF);

    prev.resize(num_v);
    std::fill(prev.begin(), prev.end(), -1);

    // get<0>(T): cost
    // get<1>(T): index
    // get<2>(T): ... ( for extent)
    using Tup = tuple<T, int>;
    priority_queue<Tup, vector<Tup>, greater<Tup>> que;

    que.emplace(0, start);
    result[start] = 0;

    while (!que.empty()) {
      Tup p = que.top();
      que.pop();

      T t = get<0>(p);
      int v = get<1>(p);

      // queueに入れてから別の最短経路が見つかった場合、探索処理は不要
      if (result[v] != t) {
        continue;
      }

      // vの各辺に対しよりコストの低い経路があるかを確認
      for (auto& e : G[v]) {
        if (result[e.to] > result[v] + e.cost) {
          prev[e.to] = v;
          result[e.to] = result[v] + e.cost;
          que.emplace(result[v] + e.cost, e.to);
        }
      }
    }
  }

  // t: 目的地
  vector<int> get_path(const vector<int>& prev, int t) {
    vector<int> path;

    for (int v = t; v != -1; v = prev[v]) {
      path.push_back(v);
    }

    reverse(path.begin(), path.end());
    return path;
  }
};

概要

制約

経路復元

ライブラリ

関連問題