重みあり単一始点最短経路 (Single Source Shortest Path in Unweighted Graph, SPFA)
(src/graph/single-source-shortest-path/in-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-weighted-graph.hpp"

Appendix

単一始点最短経路問題の solver の細かい仕様について

テンプレートパラメータに渡すグラフ $G$ の仕様について

コンストラクタ

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

頂点 $s$ からの重みあり単一始点最短経路問題を解く。

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

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

計算量

• $O(|V| |E|)$

get_original_graph

G get_original_graph() const

もとのグラフを返す。

inf

static cost_type inf()

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

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

negative_inf

static cost_type negative_inf()

$s$ から $v$ への経路に負閉路が含まれる場合の最短経路のコストとして定義されている値を返す。

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

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

static usize undefined()

構成された最短経路木において親が存在しない、または経路上に負閉路が含まれるときに返される値。

内部では 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

• size alias (src/cpp-template/header/size-alias.hpp)
• 動的なグラフ構造体 (src/graph/class/dynamic-graph.hpp)

Verified with

• test/aoj/grl_1_b/dynamic-graph.test.cpp
• test/aoj/grl_1_b/static-graph.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/class/dynamic-graph.hpp"

#include <limits>
#include <queue>
#include <vector>

namespace luz::sssp {

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

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

    graph g;
    usize g_size;
    usize source;

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

    void spfa(usize s) {
      std::queue< usize > que;
      std::vector< usize > ds_update_cnt(g_size);
      std::vector< bool > in_que(g_size);

      ds[s]            = 0;
      in_que[s]        = true;
      ds_update_cnt[s] = 0;
      que.emplace(s);

      while (not que.empty()) {
        usize v = que.front();
        que.pop();
        in_que[v] = false;

        for (const auto &e: g[v]) {
          usize u        = e.to;
          cost_type cost = e.cost;
          if (ds[v] + cost >= ds[u]) {
            continue;
          }

          ds[u]      = ds[v] + cost;
          parents[u] = v;
          ids[u]     = e.id;

          if (in_que[u]) {
            continue;
          }

          in_que[u] = true;
          ds_update_cnt[u]++;

          if (ds_update_cnt[u] < 2 * g_size) {
            que.emplace(u);
          }
        }
      }

      for (usize v: rep(0, g_size)) {
        if (ds_update_cnt[v] >= g_size) {
          ds[v]      = negative_inf();
          parents[v] = undefined();
          ids[v]     = undefined();
        }
      }
    }

   public:
    explicit InWeightedGraph(const graph &g_, usize source_)
        : g(g_),
          g_size(g.size()),
          source(source_),
          ds(g_size, inf()),
          parents(g_size, undefined()),
          ids(g_size, undefined()) {
      spfa(source);
    }

    graph get_original_graph() const {
      return g;
    }

    static inline cost_type inf() {
      return inf_;
    }

    static inline cost_type negative_inf() {
      return negative_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-weighted-graph.hpp"

#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 2 "src/graph/class/dynamic-graph.hpp"

#line 4 "src/graph/class/dynamic-graph.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename Edge >
  class DynamicGraph {

    using Edges = std::vector< Edge >;

   protected:
    std::vector< Edges > g;
    usize edge_count;

   public:
    using cost_type = typename Edge::cost_type;

    DynamicGraph() = default;
    explicit DynamicGraph(usize n): g(n), edge_count(0) {}

    usize size() const {
      return g.size();
    }

    void add_directed_edge(usize from, usize to, cost_type cost = 1) {
      assert(from < size());
      assert(to < size());
      g[from].emplace_back(from, to, cost, edge_count++);
    }

    void add_undirected_edge(usize u, usize v, cost_type cost = 1) {
      assert(u < size());
      assert(v < size());
      assert(u != v);
      g[u].emplace_back(u, v, cost, edge_count);
      g[v].emplace_back(v, u, cost, edge_count++);
    }

    Edges operator[](const usize &v) {
      return g[v];
    }

    const Edges operator[](const usize &v) const {
      return g[v];
    }
  };

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

#include <limits>
#include <queue>
#line 9 "src/graph/single-source-shortest-path/in-weighted-graph.hpp"

namespace luz::sssp {

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

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

    graph g;
    usize g_size;
    usize source;

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

    void spfa(usize s) {
      std::queue< usize > que;
      std::vector< usize > ds_update_cnt(g_size);
      std::vector< bool > in_que(g_size);

      ds[s]            = 0;
      in_que[s]        = true;
      ds_update_cnt[s] = 0;
      que.emplace(s);

      while (not que.empty()) {
        usize v = que.front();
        que.pop();
        in_que[v] = false;

        for (const auto &e: g[v]) {
          usize u        = e.to;
          cost_type cost = e.cost;
          if (ds[v] + cost >= ds[u]) {
            continue;
          }

          ds[u]      = ds[v] + cost;
          parents[u] = v;
          ids[u]     = e.id;

          if (in_que[u]) {
            continue;
          }

          in_que[u] = true;
          ds_update_cnt[u]++;

          if (ds_update_cnt[u] < 2 * g_size) {
            que.emplace(u);
          }
        }
      }

      for (usize v: rep(0, g_size)) {
        if (ds_update_cnt[v] >= g_size) {
          ds[v]      = negative_inf();
          parents[v] = undefined();
          ids[v]     = undefined();
        }
      }
    }

   public:
    explicit InWeightedGraph(const graph &g_, usize source_)
        : g(g_),
          g_size(g.size()),
          source(source_),
          ds(g_size, inf()),
          parents(g_size, undefined()),
          ids(g_size, undefined()) {
      spfa(source);
    }

    graph get_original_graph() const {
      return g;
    }

    static inline cost_type inf() {
      return inf_;
    }

    static inline cost_type negative_inf() {
      return negative_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

Back to top page