Shortest path tree (tools/shortest_path_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-02-23 20:12:17+09:00
• Include: #include "tools/shortest_path_tree.hpp"

It represents the answer to the single source shortest path problem. Let $T$ be the set of vertices whose shortest distance from vertex $s$ is finite, then it is known that the graph constructed using only the edges included in the shortest path from vertex $s$ to vertex $t \in T$ is a rooted tree with root $s$. It is the data structure that combines the rooted tree (called the shortest path tree) and the vertices not included in $T$.

License

• CC0

Author

• anqooqie

Constructor

shortest_path_tree<Cost, F> graph(std::ranges::range d, std::rangs::range p, F f);

Given $(d_0, d_1, \ldots, d_{n - 1})$, the shortest distance from a single source to vertex $v$ $(0 \leq v < n)$, and $(p_0, p_1, \ldots, p_{n - 1})$, the edge number from the parent of vertex $v$ to vertex $v$ in the shortest path tree $(0 \leq v < n)$, it creates a data structure representing the answer to the single source shortest path problem. If vertex $v$ is the root of the shortest path tree or is not in the shortest path tree, $p_v$ must be $-1$.

$f$ is a function to find the parent of vertex $v$ in the shortest path tree. For all $v$ such that vertex $v$ is a vertex in the shortest path tree but not the root, $f(p_v, v)$ must return the parent of $v$.

The type parameter <Cost> represents the type of the shortest distance.

Constraints

• $|d| = |p|$ (hereinafter referred to as $n$)
• $\forall p_v \in p. p_v \geq -1$
• $\forall p_v \in p. (p_v \geq 0 \Rightarrow 0 \leq f(p_v, v) < n)$
• For all $v$ such that $0 \leq v < n$, while (p[v] >= 0) v = f(p[v], v); halts.

Time Complexity

• $O(n)$

size

int graph.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

dist

(1) std::vector<Cost> graph.dist();
(2) Cost graph.dist(int v);

• (1)
  • It returns $d$.
• (2)
  • It returns $d_v$.

Constraints

• (1)
  • None
• (2)
  • $0 \leq v < n$

Time Complexity

• $O(1)$

from_vertex

int graph.from_vertex(int v);

It returns

\[\begin{align*} \left\{\begin{array}{ll} f(p_v, v) & \text{(if $p_v \geq 0$)}\\ -1 & \text{(if $p_v = -1$)} \end{array}\right.& \end{align*}\]

Constraints

• $0 \leq v < n$

Time Complexity

• $O(1)$

from_edge_id

int graph.from_edge_id(int v);

It returns $p_v$.

Constraints

• $0 \leq v < n$

Time Complexity

• $O(1)$

vertex_path

std::vector<int> graph.vertex_path(int v);

If $d_v$ is finite, it returns the vertices in the shortest path from the single source to vertex $v$, in the order of their appearance in the path. If $d_v$ is not finite, it returns an empty vector.

Constraints

• $0 \leq v < n$

Time Complexity

• $O(n)$

edge_id_path

std::vector<int> graph.edge_id_path(int v);

If $d_v$ is finite, it returns the edge numbers in the shortest path from the single source to vertex $v$, in the order of their appearance in the path. If $d_v$ is not finite, it returns an empty vector.

Constraints

• $0 \leq v < n$

Time Complexity

• $O(n)$

Required by

• Bellman-Ford algorithm (tools/bellman_ford.hpp)
• Dijkstra's algorithm (tools/dijkstra.hpp)
• Dijkstra's algorithm for dense graph (tools/naive_dijkstra.hpp)
• 01-BFS (tools/zero_one_bfs.hpp)

Verified with

• tests/bellman_ford.test.cpp
• tests/dijkstra/directed.test.cpp
• tests/dijkstra/undirected.test.cpp
• tests/naive_dijkstra.test.cpp
• tests/zero_one_bfs/directed.test.cpp
• tests/zero_one_bfs/undirected.test.cpp

Code

#ifndef TOOLS_SHORTEST_PATH_TREE
#define TOOLS_SHORTEST_PATH_TREE

#include <algorithm>
#include <cassert>
#include <iterator>
#include <ranges>
#include <utility>
#include <vector>

namespace tools {
  template <typename Cost, typename F>
  class shortest_path_tree {
    ::std::vector<Cost> m_dist;
    ::std::vector<int> m_from;
    F m_get_vertex;

  public:
    shortest_path_tree() = default;
    template <::std::ranges::range R1, ::std::ranges::range R2>
    shortest_path_tree(R1&& d, R2&& p, const F& f) : m_get_vertex(f) {
      ::std::ranges::copy(d, ::std::back_inserter(this->m_dist));
      ::std::ranges::copy(p, ::std::back_inserter(this->m_from));
      assert(this->m_dist.size() == this->m_from.size());
      assert(::std::ranges::all_of(this->m_from, [](const auto p_i) { return p_i >= -1; }));
    }

    int size() const {
      return this->m_dist.size();
    }
    const ::std::vector<Cost>& dist() const & {
      return this->m_dist;
    }
    ::std::vector<Cost> dist() && {
      return ::std::move(this->m_dist);
    }
    Cost dist(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_dist[v];
    }
    int from_vertex(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_from[v] >= 0 ? this->m_get_vertex(this->m_from[v], v) : -1;
    }
    int from_edge_id(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_from[v];
    }
    ::std::vector<int> vertex_path(const int v) const {
      assert(0 <= v && v < this->size());
      ::std::vector<int> path;
      for (int u = v; u >= 0; u = this->from_vertex(u)) {
        path.push_back(u);
      }
      ::std::ranges::reverse(path);
      return path;
    }
    ::std::vector<int> edge_id_path(const int v) const {
      assert(0 <= v && v < this->size());
      ::std::vector<int> path;
      for (int u = v; this->m_from[u] >= 0; u = this->from_vertex(u)) {
        path.push_back(this->m_from[u]);
      }
      ::std::ranges::reverse(path);
      return path;
    }
  };

  template <::std::ranges::range R1, ::std::ranges::range R2, typename F>
  shortest_path_tree(R1&&, R2&&, const F&) -> shortest_path_tree<::std::ranges::range_value_t<R1>, F>;
}

#endif

#line 1 "tools/shortest_path_tree.hpp"



#include <algorithm>
#include <cassert>
#include <iterator>
#include <ranges>
#include <utility>
#include <vector>

namespace tools {
  template <typename Cost, typename F>
  class shortest_path_tree {
    ::std::vector<Cost> m_dist;
    ::std::vector<int> m_from;
    F m_get_vertex;

  public:
    shortest_path_tree() = default;
    template <::std::ranges::range R1, ::std::ranges::range R2>
    shortest_path_tree(R1&& d, R2&& p, const F& f) : m_get_vertex(f) {
      ::std::ranges::copy(d, ::std::back_inserter(this->m_dist));
      ::std::ranges::copy(p, ::std::back_inserter(this->m_from));
      assert(this->m_dist.size() == this->m_from.size());
      assert(::std::ranges::all_of(this->m_from, [](const auto p_i) { return p_i >= -1; }));
    }

    int size() const {
      return this->m_dist.size();
    }
    const ::std::vector<Cost>& dist() const & {
      return this->m_dist;
    }
    ::std::vector<Cost> dist() && {
      return ::std::move(this->m_dist);
    }
    Cost dist(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_dist[v];
    }
    int from_vertex(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_from[v] >= 0 ? this->m_get_vertex(this->m_from[v], v) : -1;
    }
    int from_edge_id(const int v) const {
      assert(0 <= v && v < this->size());
      return this->m_from[v];
    }
    ::std::vector<int> vertex_path(const int v) const {
      assert(0 <= v && v < this->size());
      ::std::vector<int> path;
      for (int u = v; u >= 0; u = this->from_vertex(u)) {
        path.push_back(u);
      }
      ::std::ranges::reverse(path);
      return path;
    }
    ::std::vector<int> edge_id_path(const int v) const {
      assert(0 <= v && v < this->size());
      ::std::vector<int> path;
      for (int u = v; this->m_from[u] >= 0; u = this->from_vertex(u)) {
        path.push_back(this->m_from[u]);
      }
      ::std::ranges::reverse(path);
      return path;
    }
  };

  template <::std::ranges::range R1, ::std::ranges::range R2, typename F>
  shortest_path_tree(R1&&, R2&&, const F&) -> shortest_path_tree<::std::ranges::range_value_t<R1>, F>;
}

Back to top page