Graph/Weighed_Digraph/Dijkstra.hpp

• View this file on GitHub
• Last update: 2025-08-16 20:33:32+09:00
• Include: #include "Graph/Weighed_Digraph/Dijkstra.hpp"

Depends on

• Graph/Weighed_Digraph/Weighted_Digraph.hpp

Verified with

• verify/yosupo_library_checker/graph/Directed_Dijkstra.test.cpp

Code

#pragma once
#include"Weighted_Digraph.hpp"

namespace Weighted_Digraph::Dijkstra {
    class UnreachableException : public exception {
      public: // publicに指定
      const char* what() const noexcept override { return "求めるパスが存在しません"; }
    };

  template<typename W>
  struct Shortest_Path {
    vector<int> path_arc_ids;
    vector<int> path_vertices;
    W length;

    Shortest_Path<W>(vector<int> path_arc_ids, vector<int> path_vertices, W length):
      path_arc_ids(path_arc_ids), path_vertices(path_vertices), length(length) {}
  };

  template<typename W>
  Shortest_Path<W> Dijkstra(Weighted_Digraph<W> &D, int start, int goal) {
    int n = D.order();

    vector<bool> reachable(n, false); reachable[start] = true;
    vector<int> parent_arc_ids(n, -1);
    vector<W> dist(n); dist[start] = 0;

    using P = pair<W, int>;
    priority_queue<P, vector<P>, greater<P>> Q; Q.emplace(dist[start], start);

    while (!Q.empty()) {
      P pair = Q.top(); Q.pop();
      W d = pair.first;
      int v = pair.second;

      if (dist[v] < d) { continue; }

      for (auto arc_id: D.successors(v)) {
        Weighted_Arc<W> arc = D.get_arc(arc_id);
        if (!reachable[arc.target] || dist[arc.target] > dist[v] + arc.weight) {
          dist[arc.target] = dist[v] + arc.weight;
          reachable[arc.target] = true;
          parent_arc_ids[arc.target] = arc.id;
          Q.emplace(dist[arc.target], arc.target);
        }
      }
    }

    if (!reachable[goal]) { throw UnreachableException(); }

    vector<int> path_arc_ids;
    vector<int> path_vertices{goal}; 

    while (path_vertices.back() != start) {
      int arc_id = parent_arc_ids[path_vertices.back()];
      auto arc = D.get_arc(arc_id);

      path_arc_ids.emplace_back(arc_id);
      path_vertices.emplace_back(arc.source);
    }

    reverse(path_arc_ids.begin(), path_arc_ids.end());
    reverse(path_vertices.begin(), path_vertices.end());

    return Shortest_Path<W>(path_arc_ids, path_vertices, dist[goal]);
  }
}

#line 2 "Graph/Weighed_Digraph/Weighted_Digraph.hpp"

namespace Weighted_Digraph {
  template<typename W>
  struct Weighted_Arc {
    int id, source, target;
    W weight;

    Weighted_Arc (int id, int source, int target, W weight): id(id), source(source), target(target), weight(weight) {}
  };

  template<typename W>
  class Weighted_Digraph {
    using Arc = Weighted_Arc<W>;

    private:
    int arc_id_offset;
    vector<vector<int>> adjacent_out, adjacent_in;
    vector<Arc> arcs;

    public:
    Weighted_Digraph(int n, int arc_id_offset = 0): arc_id_offset(arc_id_offset) {
        adjacent_out.assign(n, {});
        adjacent_in.assign(n, {});
        arcs.resize(arc_id_offset, Weighted_Arc<W>(-1, -1, -1, W()));
      }
    
    inline int order() const { return int(adjacent_in.size()); }

    inline int size() const { return int(arcs.size()) - arc_id_offset; }

    // 頂点 u から頂点 v への重み w の弧を追加する.
    int add_arc(int u, int v, W w){
      int id = int(arcs.size());

      adjacent_out[u].emplace_back(id);
      adjacent_in[v].emplace_back(id);
      arcs.emplace_back(id, u, v, w);

      return id;
    }

    // 頂点 u から出る弧の ID のリストを取得
    inline const std::vector<int>& successors(int u) const { return adjacent_out[u]; }

    // 頂点 u に入る弧の ID のリストを取得
    inline const std::vector<int>& predecessors(int u) const { return adjacent_in[u]; }

    // 弧 ID が id である弧を取得する.
    inline const Arc& get_arc(int id) const { return arcs[id]; }
    inline Arc& get_arc(int id) { return arcs[id]; }
  };
}
#line 3 "Graph/Weighed_Digraph/Dijkstra.hpp"

namespace Weighted_Digraph::Dijkstra {
    class UnreachableException : public exception {
      public: // publicに指定
      const char* what() const noexcept override { return "求めるパスが存在しません"; }
    };

  template<typename W>
  struct Shortest_Path {
    vector<int> path_arc_ids;
    vector<int> path_vertices;
    W length;

    Shortest_Path<W>(vector<int> path_arc_ids, vector<int> path_vertices, W length):
      path_arc_ids(path_arc_ids), path_vertices(path_vertices), length(length) {}
  };

  template<typename W>
  Shortest_Path<W> Dijkstra(Weighted_Digraph<W> &D, int start, int goal) {
    int n = D.order();

    vector<bool> reachable(n, false); reachable[start] = true;
    vector<int> parent_arc_ids(n, -1);
    vector<W> dist(n); dist[start] = 0;

    using P = pair<W, int>;
    priority_queue<P, vector<P>, greater<P>> Q; Q.emplace(dist[start], start);

    while (!Q.empty()) {
      P pair = Q.top(); Q.pop();
      W d = pair.first;
      int v = pair.second;

      if (dist[v] < d) { continue; }

      for (auto arc_id: D.successors(v)) {
        Weighted_Arc<W> arc = D.get_arc(arc_id);
        if (!reachable[arc.target] || dist[arc.target] > dist[v] + arc.weight) {
          dist[arc.target] = dist[v] + arc.weight;
          reachable[arc.target] = true;
          parent_arc_ids[arc.target] = arc.id;
          Q.emplace(dist[arc.target], arc.target);
        }
      }
    }

    if (!reachable[goal]) { throw UnreachableException(); }

    vector<int> path_arc_ids;
    vector<int> path_vertices{goal}; 

    while (path_vertices.back() != start) {
      int arc_id = parent_arc_ids[path_vertices.back()];
      auto arc = D.get_arc(arc_id);

      path_arc_ids.emplace_back(arc_id);
      path_vertices.emplace_back(arc.source);
    }

    reverse(path_arc_ids.begin(), path_arc_ids.end());
    reverse(path_vertices.begin(), path_vertices.end());

    return Shortest_Path<W>(path_arc_ids, path_vertices, dist[goal]);
  }
}

Back to top page