Bellman-Ford algorithm (tools/bellman_ford.hpp)

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

It solves the single source shortest path problem on a given directed graph which is not necessarily simple. The graph can have negative cycles.

License

• CC0

Author

• anqooqie

Constructor

bellman_ford<T> graph(int n);

It creates a directed graph with $n$ vertices and $0$ edges. The type parameter <T> represents the type of the cost.

Constraints

• $n \geq 0$

Time Complexity

• $O(n)$

size

int graph.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

add_edge

int graph.add_edge(int u, int v, T w);

It adds an edge oriented from $u$ to $v$ with cost w. It returns an integer $k$ such that this is the $k$-th ($0$ indexed) edge that is added.

Constraints

• $0 \leq u < n$
• $0 \leq v < n$

Time Complexity

• $O(1)$ amortized

get_edge

struct edge {
  int from;
  int to;
  T cost;
};
edge graph.get_edge(int k);

It returns the $k$-th ($0$ indexed) edge.

Constraints

• $0 \leq k < |E|$ where $|E|$ is the number of edges

Time Complexity

• $O(1)$

edges

std::vector<edge> graph.edges();

It returns all the edges in the graph. The edges are ordered in the same order as added by add_edge.

Constraints

• None

Time Complexity

• $O(1)$

query

(1) std::vector<T> graph.query(int s);
(2) std::vector<T> graph.query<false>(int s);
(3) tools::shortest_path_tree<T, (anonymous type)> graph.query<true>(int s);

• (1), (2)
  • It is identical to graph.query<true>(s).dist().
• (3)
  • It returns the answer to the single source shortest path problem from a source vertex $s$.

Constraints

• $0 \leq s < n$

Time Complexity

• $O(n|E|)$ where $|E|$ is the number of edges

Depends on

• chmin function (tools/chmin.hpp)
• Shortest path tree (tools/shortest_path_tree.hpp)

Verified with

• tests/bellman_ford.test.cpp

Code

#ifndef TOOLS_BELLMAN_FORD_HPP
#define TOOLS_BELLMAN_FORD_HPP

#include <cassert>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>
#include "tools/chmin.hpp"
#include "tools/shortest_path_tree.hpp"

namespace tools {

  template <typename T>
  class bellman_ford {
  public:
    struct edge {
      int from;
      int to;
      T cost;
    };

  private:
    int m_size;
    ::std::vector<edge> m_edges;

  public:
    bellman_ford() = default;
    explicit bellman_ford(const int n) : m_size(n) {
    }

    int size() const {
      return this->m_size;
    }

    int add_edge(const int u, const int v, const T w) {
      assert(0 <= u && u < this->size());
      assert(0 <= v && v < this->size());
      this->m_edges.push_back({u, v, w});
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const int k) const & {
      assert(0 <= k && k < ::std::ssize(this->m_edges));
      return this->m_edges[k];
    }
    edge get_edge(const int k) && {
      assert(0 <= k && k < ::std::ssize(this->m_edges));
      return ::std::move(this->m_edges[k]);
    }

    const ::std::vector<edge>& edges() const & {
      return this->m_edges;
    }
    ::std::vector<edge> edges() && {
      return ::std::move(this->m_edges);
    }

    template <bool Restore = false>
    auto query(const int s) const {
      assert(0 <= s && s < this->size());

      ::std::vector<T> dist(this->size(), ::std::numeric_limits<T>::max());
      dist[s] = 0;
      ::std::vector<int> prev(Restore ? this->size() : 0, -1);

      for (int i = 0; i + 1 < this->size(); ++i) {
        for (int k = 0; k < ::std::ssize(this->m_edges); ++k) {
          const auto& edge = this->m_edges[k];
          if (dist[edge.from] < ::std::numeric_limits<T>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + edge.cost)) {
            if constexpr (Restore) {
              prev[edge.to] = k;
            }
          }
        }
      }
      for (int k = 0; k < ::std::ssize(this->m_edges); ++k) {
        const auto& edge = this->m_edges[k];
        if (dist[edge.from] < ::std::numeric_limits<T>::max() && dist[edge.from] + (dist[edge.from] > ::std::numeric_limits<T>::lowest() ? edge.cost : 0) < dist[edge.to]) {
          dist[edge.to] = ::std::numeric_limits<T>::lowest();
          if constexpr (Restore) {
            prev[edge.to] = -1;
          }
        }
      }
      for (int i = 0; i + 1 < this->size(); ++i) {
        for (int k = 0; k < ::std::ssize(this->m_edges); ++k) {
          const auto& edge = this->m_edges[k];
          if (dist[edge.from] < ::std::numeric_limits<T>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + (dist[edge.from] > ::std::numeric_limits<T>::lowest() ? edge.cost : 0))) {
            if constexpr (Restore) {
              prev[edge.to] = -1;
            }
          }
        }
      }

      if constexpr (Restore) {
        return ::tools::shortest_path_tree(dist, prev, [&](const auto e, auto) {
          return this->m_edges[e].from;
        });
      } else {
        return dist;
      }
    }
  };
}

#endif

#line 1 "tools/bellman_ford.hpp"



#include <cassert>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>
#line 1 "tools/chmin.hpp"



#include <type_traits>
#line 6 "tools/chmin.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/shortest_path_tree.hpp"



#include <algorithm>
#line 7 "tools/shortest_path_tree.hpp"
#include <ranges>
#line 10 "tools/shortest_path_tree.hpp"

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>;
}


#line 11 "tools/bellman_ford.hpp"

namespace tools {

  template <typename T>
  class bellman_ford {
  public:
    struct edge {
      int from;
      int to;
      T cost;
    };

  private:
    int m_size;
    ::std::vector<edge> m_edges;

  public:
    bellman_ford() = default;
    explicit bellman_ford(const int n) : m_size(n) {
    }

    int size() const {
      return this->m_size;
    }

    int add_edge(const int u, const int v, const T w) {
      assert(0 <= u && u < this->size());
      assert(0 <= v && v < this->size());
      this->m_edges.push_back({u, v, w});
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const int k) const & {
      assert(0 <= k && k < ::std::ssize(this->m_edges));
      return this->m_edges[k];
    }
    edge get_edge(const int k) && {
      assert(0 <= k && k < ::std::ssize(this->m_edges));
      return ::std::move(this->m_edges[k]);
    }

    const ::std::vector<edge>& edges() const & {
      return this->m_edges;
    }
    ::std::vector<edge> edges() && {
      return ::std::move(this->m_edges);
    }

    template <bool Restore = false>
    auto query(const int s) const {
      assert(0 <= s && s < this->size());

      ::std::vector<T> dist(this->size(), ::std::numeric_limits<T>::max());
      dist[s] = 0;
      ::std::vector<int> prev(Restore ? this->size() : 0, -1);

      for (int i = 0; i + 1 < this->size(); ++i) {
        for (int k = 0; k < ::std::ssize(this->m_edges); ++k) {
          const auto& edge = this->m_edges[k];
          if (dist[edge.from] < ::std::numeric_limits<T>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + edge.cost)) {
            if constexpr (Restore) {
              prev[edge.to] = k;
            }
          }
        }
      }
      for (int k = 0; k < ::std::ssize(this->m_edges); ++k) {
        const auto& edge = this->m_edges[k];
        if (dist[edge.from] < ::std::numeric_limits<T>::max() && dist[edge.from] + (dist[edge.from] > ::std::numeric_limits<T>::lowest() ? edge.cost : 0) < dist[edge.to]) {
          dist[edge.to] = ::std::numeric_limits<T>::lowest();
          if constexpr (Restore) {
            prev[edge.to] = -1;
          }
        }
      }
      for (int i = 0; i + 1 < this->size(); ++i) {
        for (int k = 0; k < ::std::ssize(this->m_edges); ++k) {
          const auto& edge = this->m_edges[k];
          if (dist[edge.from] < ::std::numeric_limits<T>::max() && ::tools::chmin(dist[edge.to], dist[edge.from] + (dist[edge.from] > ::std::numeric_limits<T>::lowest() ? edge.cost : 0))) {
            if constexpr (Restore) {
              prev[edge.to] = -1;
            }
          }
        }
      }

      if constexpr (Restore) {
        return ::tools::shortest_path_tree(dist, prev, [&](const auto e, auto) {
          return this->m_edges[e].from;
        });
      } else {
        return dist;
      }
    }
  };
}

Back to top page