非負重み単一始点最短経路 (Single Source Shortest Path in Non-negative Weighted Graph, Dijkstra's Algorithm)
(src/graph/single-source-shortest-path/in-non-negative-weighted-graph.hpp)

View this file on GitHub
Last update: 2023-07-30 00:54:52+09:00
Include: #include "src/graph/single-source-shortest-path/in-non-negative-weighted-graph.hpp"

Appendix

コンストラクタ

sssp::InNonNegativeWeightedGraph(const G &g, usize s)

負辺がないようなグラフ $G$ において、頂点 $s$ からの単一始点最短経路問題を解く。

コンストラクタ内部では以下が行われている。

始点から各頂点への最短経路のコストの計算
以下で特定される最短経路木を一つ構成
- 親の頂点番号
- 親との間にある辺の辺番号

制約

各辺のコストは非負整数である。
任意の頂点について $s$ からの最短経路のコストが cost_type に収まる。

計算量

$O((|E| + |V|) \log |V|)$

get_original_graph

G get_original_graph() const

もとのグラフを返す。

inf

cost_type inf() const

$s$ からの経路が存在しないような頂点 $v$ への $s$ からの最短経路のコストとして定義されている値を返す。

内部では std::numeric_limits< cost_type >::max() によって定義されている。

distance

cost_type distance(const usize v) const

$s$ から $v$ への最短経路のコストを返す。経路が存在しない場合のコストは inf() として定義されている。

get_distances

std::vector< cost_type > get_distances() const

各頂点に対する distance を std::vector で wrap して返す。distance(v) は v 番目の要素として表される。

$s$ からの経路が存在しないような頂点へのコストは inf() として定義されている。

undefined

usize undefined() const

構成された最短経路木において親が存在しないときに返される値。

内部では std::numeric_limits< usize >::max() によって定義されている。

parent

usize parent(const usize v) const

構成された最短経路木においての v の親を返す。

親が存在しない場合 undefined() が返される。

get_parents

std::vector< usize > get_parents() const

各頂点に対する parent を std::vector で wrap して返す。parent(v) は v 番目の要素として表される。

親が存在しないような頂点の場合は undefined() となる。

edge_label

usize edge_label(const usize v) const

構成された最短経路木における v とその親との間にある辺の、もとのグラフでの辺番号を返す。

親が存在しない場合 undefined() が返される。

get_edge_labels

usize get_edge_labels() const

各頂点に対する edge_label(v) を std::vector で wrap して返す。edge_label(v) は v 番目の要素として表される。

親が存在しないような頂点に対応する要素は undefined() となる。

Depends on

Verified with

Code

#pragma once

#include "src/cpp-template/header/change-min.hpp"
#include "src/cpp-template/header/size-alias.hpp"

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

namespace luz::sssp {

  template < class G >
  class InNonNegativeWeightedGraph {
    using cost_type = typename G::cost_type;
    using graph     = G;

    static constexpr usize undefined_ =
        std::numeric_limits< usize >::max();
    static constexpr cost_type inf_ =
        std::numeric_limits< cost_type >::max();

    graph g;
    usize g_size;
    std::vector< cost_type > ds;
    std::vector< usize > parents, ids;

    void dijkstra(usize s) {
      using pq_type = std::pair< cost_type, usize >;
      std::priority_queue< pq_type, std::vector< pq_type >,
                           std::greater< pq_type > >
          pq;

      ds[s] = 0;
      pq.emplace(ds[s], s);

      while (not pq.empty()) {
        auto [cost, v] = pq.top();
        pq.pop();

        if (ds[v] < cost) continue;
        for (auto &e: g[v]) {
          if (chmin(ds[e.to], cost + e.cost)) {
            pq.emplace(ds[e.to], e.to);
            parents[e.to] = v;
            ids[e.to]     = e.id;
          }
        }
      }
    }

   public:
    explicit InNonNegativeWeightedGraph(const graph &g_, usize source)
        : g(g_),
          g_size(g.size()),
          ds(g_size, inf_),
          parents(g_size, undefined_),
          ids(g_size, undefined_) {
      dijkstra(source);
    }

    inline graph get_original_graph() const {
      return g;
    }

    static inline cost_type inf() {
      return inf_;
    }

    inline cost_type distance(const usize v) const {
      return ds[v];
    }

    inline std::vector< cost_type > get_distances() const {
      return ds;
    }

    static inline usize undefined() {
      return undefined_;
    }

    inline usize parent(const usize v) const {
      return parents[v];
    }

    inline std::vector< usize > get_parents() const {
      return parents;
    }

    inline usize edge_label(const usize v) const {
      return ids[v];
    }

    inline std::vector< usize > get_edge_labels() const {
      return ids;
    }
  };

} // namespace luz::sssp

#line 2 "src/graph/single-source-shortest-path/in-non-negative-weighted-graph.hpp"

#line 2 "src/cpp-template/header/change-min.hpp"

namespace luz {

  template < typename T1, typename T2 >
  inline bool chmin(T1 &a, T2 b) {
    return a > b and (a = b, true);
  }

} // namespace luz
#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 5 "src/graph/single-source-shortest-path/in-non-negative-weighted-graph.hpp"

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

namespace luz::sssp {

  template < class G >
  class InNonNegativeWeightedGraph {
    using cost_type = typename G::cost_type;
    using graph     = G;

    static constexpr usize undefined_ =
        std::numeric_limits< usize >::max();
    static constexpr cost_type inf_ =
        std::numeric_limits< cost_type >::max();

    graph g;
    usize g_size;
    std::vector< cost_type > ds;
    std::vector< usize > parents, ids;

    void dijkstra(usize s) {
      using pq_type = std::pair< cost_type, usize >;
      std::priority_queue< pq_type, std::vector< pq_type >,
                           std::greater< pq_type > >
          pq;

      ds[s] = 0;
      pq.emplace(ds[s], s);

      while (not pq.empty()) {
        auto [cost, v] = pq.top();
        pq.pop();

        if (ds[v] < cost) continue;
        for (auto &e: g[v]) {
          if (chmin(ds[e.to], cost + e.cost)) {
            pq.emplace(ds[e.to], e.to);
            parents[e.to] = v;
            ids[e.to]     = e.id;
          }
        }
      }
    }

   public:
    explicit InNonNegativeWeightedGraph(const graph &g_, usize source)
        : g(g_),
          g_size(g.size()),
          ds(g_size, inf_),
          parents(g_size, undefined_),
          ids(g_size, undefined_) {
      dijkstra(source);
    }

    inline graph get_original_graph() const {
      return g;
    }

    static inline cost_type inf() {
      return inf_;
    }

    inline cost_type distance(const usize v) const {
      return ds[v];
    }

    inline std::vector< cost_type > get_distances() const {
      return ds;
    }

    static inline usize undefined() {
      return undefined_;
    }

    inline usize parent(const usize v) const {
      return parents[v];
    }

    inline std::vector< usize > get_parents() const {
      return parents;
    }

    inline usize edge_label(const usize v) const {
      return ids[v];
    }

    inline std::vector< usize > get_edge_labels() const {
      return ids;
    }
  };

} // namespace luz::sssp

非負重み単一始点最短経路 (Single Source Shortest Path in Non-negative Weighted Graph, Dijkstra's Algorithm) (src/graph/single-source-shortest-path/in-non-negative-weighted-graph.hpp)