graph/dijkstra.hpp

• View this file on GitHub
• Last update: 2023-11-10 15:24:24+09:00
• Include: #include "graph/dijkstra.hpp"

Depends on

• Graph Template (graph/template.hpp)

Verified with

• test/yosupo/Graph/Shortest-Path.test.cpp

Code

#include "template.hpp"

template <class T, class U = T>
void dijkstra(const Graph<T> &root, const int s, vector<U> &dist, vector<int> &prev){
  const int n = root.size();
  dist.assign(n, numeric_limits<U>::max());
  prev.assign(n, -1);
  using pui = pair<U, int>;
  priority_queue<pui, vector<pui>, greater<pui>> que;
  que.push({ 0, s });
  while(!que.empty()){
    U val; int pos;
    tie(val,pos) = que.top();
    que.pop();
    if(dist[pos] < val) continue;
    for(const auto &x : root[pos]){
      if(chmin(dist[x], val + x.cost)){
        que.push({ dist[x], x });
        prev[x] = pos;
      }
    }
  }
}

#line 2 "graph/template.hpp"

/**
 * @brief Graph Template
*/
template <class T>
struct Edge {
  int from,to;
  T cost;
  int idx;
  Edge(){};
  Edge(int f, int t, T c=1, int i=-1) : from(f), to(t), cost(c), idx(i){}
  Edge(int t) : to(t), from(-1), cost(1), idx(-1){}
  operator int() const{ return to; }
  bool operator<(const Edge &e){ return cost < e.cost; }
};
template <class T>
struct Graph : vector<vector<Edge<T>>> {
  Graph(){}
  Graph(const int &n) : vector<vector<Edge<T>>>(n){}
  void add_edge(int a, int b, T c=1, int i=-1){
    (*this)[a].push_back({ a, b, c, i });
  }
};
using graph = Graph<int>;
#line 2 "graph/dijkstra.hpp"

template <class T, class U = T>
void dijkstra(const Graph<T> &root, const int s, vector<U> &dist, vector<int> &prev){
  const int n = root.size();
  dist.assign(n, numeric_limits<U>::max());
  prev.assign(n, -1);
  using pui = pair<U, int>;
  priority_queue<pui, vector<pui>, greater<pui>> que;
  que.push({ 0, s });
  while(!que.empty()){
    U val; int pos;
    tie(val,pos) = que.top();
    que.pop();
    if(dist[pos] < val) continue;
    for(const auto &x : root[pos]){
      if(chmin(dist[x], val + x.cost)){
        que.push({ dist[x], x });
        prev[x] = pos;
      }
    }
  }
}

Back to top page