Dijkstra
(graph/dijkstra.hpp)

• View this file on GitHub
• Last update: 2021-08-01 23:46:19+09:00
• Include: #include "graph/dijkstra.hpp"

Depends on

• graph/template.hpp

Verified with

• test/aoj/GRL_1_A.test.cpp

Code

#ifndef __GRAPH__DIJKSTRA
#define __GRAPH__DIJKSTRA
// @title Dijkstra
#include "template.hpp"

#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

template < typename T >
struct Dijkstra {
  using P = std::pair<T, int>; // <始点からの距離, 点のid>
  const T INF; // 十分に大きいがoverflowしない値として、型Tの最大値の半分を使う
  const int V; // 頂点数
  Graph<T> g;
  std::vector<T> dist; // 始点からの距離
  std::vector<bool> visit; // すでに探索済みの点か
  std::vector<int> prev; // 移動経路
  Dijkstra(Graph<T> &g): INF(std::numeric_limits<T>::max()/2), V(g.size()), g(g), dist(V), visit(V), prev(V) {}
  Dijkstra(Graph<T> &g, int V): INF(std::numeric_limits<T>::max()/2), V(V), g(g), dist(V), visit(V), prev(V) {}
  void init(int s) {
    std::fill(dist.begin(), dist.end(), INF);
    std::fill(visit.begin(), visit.end(), false);
    std::fill(prev.begin(), prev.end(), -1);
    dist[s] = T(); // 始点の距離を0で初期化
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    pq.push({dist[s], s});
    while (!pq.empty()) {
      P node = pq.top(); pq.pop();
      int from = node.second;
      if (visit[from]) continue;
      visit[from] = true;
      for (auto &e : g[from]) {
        if (visit[e.to]) continue;
        T d = node.first + e.cost;
        if (d >= dist[e.to]) continue;
        dist[e.to] = d;
        prev[e.to] = from;
        pq.push({d, e.to});
      }
    }
  }

  // 移動経路を取得
  std::vector<int> get_path(int t) {
    std::vector<int> path;
    for(; t != -1;t=prev[t]){
        path.push_back(t);
    }
    reverse(path.begin(), path.end());
    return path;
  }

};

#endif // __GRAPH__DIJKSTRA

#line 1 "graph/dijkstra.hpp"


// @title Dijkstra
#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 5 "graph/dijkstra.hpp"

#include <algorithm>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#line 12 "graph/dijkstra.hpp"

template < typename T >
struct Dijkstra {
  using P = std::pair<T, int>; // <始点からの距離, 点のid>
  const T INF; // 十分に大きいがoverflowしない値として、型Tの最大値の半分を使う
  const int V; // 頂点数
  Graph<T> g;
  std::vector<T> dist; // 始点からの距離
  std::vector<bool> visit; // すでに探索済みの点か
  std::vector<int> prev; // 移動経路
  Dijkstra(Graph<T> &g): INF(std::numeric_limits<T>::max()/2), V(g.size()), g(g), dist(V), visit(V), prev(V) {}
  Dijkstra(Graph<T> &g, int V): INF(std::numeric_limits<T>::max()/2), V(V), g(g), dist(V), visit(V), prev(V) {}
  void init(int s) {
    std::fill(dist.begin(), dist.end(), INF);
    std::fill(visit.begin(), visit.end(), false);
    std::fill(prev.begin(), prev.end(), -1);
    dist[s] = T(); // 始点の距離を0で初期化
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    pq.push({dist[s], s});
    while (!pq.empty()) {
      P node = pq.top(); pq.pop();
      int from = node.second;
      if (visit[from]) continue;
      visit[from] = true;
      for (auto &e : g[from]) {
        if (visit[e.to]) continue;
        T d = node.first + e.cost;
        if (d >= dist[e.to]) continue;
        dist[e.to] = d;
        prev[e.to] = from;
        pq.push({d, e.to});
      }
    }
  }

  // 移動経路を取得
  std::vector<int> get_path(int t) {
    std::vector<int> path;
    for(; t != -1;t=prev[t]){
        path.push_back(t);
    }
    reverse(path.begin(), path.end());
    return path;
  }

};

Back to top page