johnson.hpp

SECTIONGraph INCLUDEnoya/johnson.hpp

在含负边但无负环的稀疏有向图上求全源最短路，并保留 Dijkstra 在稀疏图上的优势。

Complexity: Time: O(VE + V(E + V) log V). Space: O(V^2 + E).

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(VE + V(E + V) log V).
/// Space: O(V^2 + E).

#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

namespace noya {

/// @brief Johnson all-pairs shortest paths for a sparse directed graph in
/// O(nm + nm log n); nullopt means the graph contains a negative cycle.
template <class Weight>
std::optional<std::vector<std::vector<std::int64_t>>>
johnson(int n, const std::vector<std::tuple<int, int, Weight>> &es) {
  assert(n >= 0);
  for (auto [u, to, w] : es) {
    (void)w;
    assert(0 <= u && u < n);
    assert(0 <= to && to < n);
  }
  std::vector<__int128> pot(n);
  for (int ite = 0; ite < n; ite++) {
    bool chg = false;
    for (auto [u, to, w] : es) {
      __int128 can = pot[u] + __int128(w);
      if (can < pot[to]) {
        pot[to] = can;
        chg = true;
        if (ite + 1 == n) {
          return std::nullopt;
        }
      }
    }
    if (!chg) {
      break;
    }
  }

  std::vector<std::vector<std::pair<int, std::int64_t>>> g(n);
  for (auto [u, to, w] : es) {
    __int128 rw = __int128(w) + pot[u] - pot[to];
    assert(rw >= 0 && rw <= std::numeric_limits<std::int64_t>::max());
    g[u].emplace_back(to, std::int64_t(rw));
  }

  const std::int64_t inf = std::numeric_limits<std::int64_t>::max();
  std::vector<std::vector<std::int64_t>> res(n,
                                             std::vector<std::int64_t>(n, inf));
  for (int s = 0; s < n; s++) {
    using state = std::pair<std::int64_t, int>;
    std::priority_queue<state, std::vector<state>, std::greater<>> q;
    std::vector<std::int64_t> dis(n, inf);
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
      auto [cur, u1] = q.top();
      q.pop();
      if (cur != dis[u1]) {
        continue;
      }
      for (auto [nxt, w] : g[u1]) {
        if (cur <= inf - w && cur + w < dis[nxt]) {
          dis[nxt] = cur + w;
          q.emplace(dis[nxt], nxt);
        }
      }
    }
    for (int t = 0; t < n; t++) {
      if (dis[t] == inf) {
        continue;
      }
      __int128 val = __int128(dis[t]) - pot[s] + pot[t];
      assert(std::numeric_limits<std::int64_t>::lowest() <= val &&
             val <= std::numeric_limits<std::int64_t>::max());
      res[s][t] = std::int64_t(val);
    }
  }
  return res;
}

} // namespace noya

#ifndef NOYA_JOHNSON_HPP
#define NOYA_JOHNSON_HPP 1

/// @complexity Time: O(VE + V(E + V) log V).
/// Space: O(V^2 + E).

#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

namespace noya {

/// @brief Johnson all-pairs shortest paths for a sparse directed graph in
/// O(nm + nm log n); nullopt means the graph contains a negative cycle.
template <class Weight>
std::optional<std::vector<std::vector<std::int64_t>>>
johnson(int n, const std::vector<std::tuple<int, int, Weight>> &es) {
  assert(n >= 0);
  for (auto [u, to, w] : es) {
    (void)w;
    assert(0 <= u && u < n);
    assert(0 <= to && to < n);
  }
  std::vector<__int128> pot(n);
  for (int ite = 0; ite < n; ite++) {
    bool chg = false;
    for (auto [u, to, w] : es) {
      __int128 can = pot[u] + __int128(w);
      if (can < pot[to]) {
        pot[to] = can;
        chg = true;
        if (ite + 1 == n) {
          return std::nullopt;
        }
      }
    }
    if (!chg) {
      break;
    }
  }

  std::vector<std::vector<std::pair<int, std::int64_t>>> g(n);
  for (auto [u, to, w] : es) {
    __int128 rw = __int128(w) + pot[u] - pot[to];
    assert(rw >= 0 && rw <= std::numeric_limits<std::int64_t>::max());
    g[u].emplace_back(to, std::int64_t(rw));
  }

  const std::int64_t inf = std::numeric_limits<std::int64_t>::max();
  std::vector<std::vector<std::int64_t>> res(n,
                                             std::vector<std::int64_t>(n, inf));
  for (int s = 0; s < n; s++) {
    using state = std::pair<std::int64_t, int>;
    std::priority_queue<state, std::vector<state>, std::greater<>> q;
    std::vector<std::int64_t> dis(n, inf);
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
      auto [cur, u1] = q.top();
      q.pop();
      if (cur != dis[u1]) {
        continue;
      }
      for (auto [nxt, w] : g[u1]) {
        if (cur <= inf - w && cur + w < dis[nxt]) {
          dis[nxt] = cur + w;
          q.emplace(dis[nxt], nxt);
        }
      }
    }
    for (int t = 0; t < n; t++) {
      if (dis[t] == inf) {
        continue;
      }
      __int128 val = __int128(dis[t]) - pot[s] + pot[t];
      assert(std::numeric_limits<std::int64_t>::lowest() <= val &&
             val <= std::numeric_limits<std::int64_t>::max());
      res[s][t] = std::int64_t(val);
    }
  }
  return res;
}

} // namespace noya

#endif // NOYA_JOHNSON_HPP

#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

/// @complexity Time: O(VE + V(E + V) log V).
/// Space: O(V^2 + E).

namespace noya {

/// @brief Johnson all-pairs shortest paths for a sparse directed graph in
/// O(nm + nm log n); nullopt means the graph contains a negative cycle.
template <class Weight>
std::optional<std::vector<std::vector<std::int64_t>>>
johnson(int n, const std::vector<std::tuple<int, int, Weight>> &es) {
  assert(n >= 0);
  for (auto [u, to, w] : es) {
    (void)w;
    assert(0 <= u && u < n);
    assert(0 <= to && to < n);
  }
  std::vector<__int128> pot(n);
  for (int ite = 0; ite < n; ite++) {
    bool chg = false;
    for (auto [u, to, w] : es) {
      __int128 can = pot[u] + __int128(w);
      if (can < pot[to]) {
        pot[to] = can;
        chg = true;
        if (ite + 1 == n) {
          return std::nullopt;
        }
      }
    }
    if (!chg) {
      break;
    }
  }

  std::vector<std::vector<std::pair<int, std::int64_t>>> g(n);
  for (auto [u, to, w] : es) {
    __int128 rw = __int128(w) + pot[u] - pot[to];
    assert(rw >= 0 && rw <= std::numeric_limits<std::int64_t>::max());
    g[u].emplace_back(to, std::int64_t(rw));
  }

  const std::int64_t inf = std::numeric_limits<std::int64_t>::max();
  std::vector<std::vector<std::int64_t>> res(n,
                                             std::vector<std::int64_t>(n, inf));
  for (int s = 0; s < n; s++) {
    using state = std::pair<std::int64_t, int>;
    std::priority_queue<state, std::vector<state>, std::greater<>> q;
    std::vector<std::int64_t> dis(n, inf);
    dis[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
      auto [cur, u1] = q.top();
      q.pop();
      if (cur != dis[u1]) {
        continue;
      }
      for (auto [nxt, w] : g[u1]) {
        if (cur <= inf - w && cur + w < dis[nxt]) {
          dis[nxt] = cur + w;
          q.emplace(dis[nxt], nxt);
        }
      }
    }
    for (int t = 0; t < n; t++) {
      if (dis[t] == inf) {
        continue;
      }
      __int128 val = __int128(dis[t]) - pot[s] + pot[t];
      assert(std::numeric_limits<std::int64_t>::lowest() <= val &&
             val <= std::numeric_limits<std::int64_t>::max());
      res[s][t] = std::int64_t(val);
    }
  }
  return res;
}

} // namespace noya