Skip to content

shortest_path.hpp

SECTIONGraph INCLUDEnoya/shortest_path.hpp

统一提供 BFS、01-BFS、Dijkstra 与 Bellman-Ford；按边权范围求单源最短路并恢复路径。

Complexity: Time: O(V + E) BFS/0-1 BFS, O((V + E) log V) Dijkstra, O(VE) signed-cycle routines. Space: O(V + E).

AC 记录：shortest_path。

跳到代码 · GitHub ↗

Implementation

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

/// @complexity Time: O(V + E) BFS/0-1 BFS, O((V + E) log V) Dijkstra, O(VE) signed-cycle routines.
/// Space: O(V + E).

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

namespace noya {
/// @brief BFS on unweighted graph. @return (distances, predecessors).
inline std::pair<std::vector<int>, std::vector<int>>
bfs_unweighted(std::vector<std::vector<int>> &g, int src) {
  int N = int(g.size());
  const int INF = std::numeric_limits<int>::max();
  std::vector<int> dis(N, INF);
  std::vector<int> pre(N, -1);
  dis[src] = 0;
  pre[src] = src;

  std::vector<int> que{src};
  for (int i = 0; i < int(que.size()); i++) {
    int u = que[i];
    for (auto v : g[u])
      if (dis[v] == INF) {
        dis[v] = dis[u] + 1;
        pre[v] = u;
        que.push_back(v);
      }
  }
  return {dis, pre};
}

/// @brief Dijkstra's algorithm. @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
dijkstra(std::vector<std::vector<T>> &g, int src) {
  int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  std::vector<int64_t> dis(N, INF);
  std::vector<int> pre(N, -1);
  std::priority_queue<std::pair<int64_t, int>,
                      std::vector<std::pair<int64_t, int>>, std::greater<>>
      que;
  que.emplace(dis[src] = 0, src);
  pre[src] = src;
  while (!que.empty()) {
    auto [d, u] = que.top();
    que.pop();
    if (d > dis[u])
      continue;
    for (auto &[v, w] : g[u])
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        pre[v] = u;
        que.emplace(dis[v], v);
      }
  }
  return {dis, pre};
}

/// @brief Shortest paths in a graph whose edge weights are 0 or 1.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
bfs01(const std::vector<std::vector<T>> &g, int src) {
  const int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  std::vector<int64_t> dis(N, INF);
  std::vector<int> pre(N, -1);
  std::deque<int> que;
  dis[src] = 0;
  pre[src] = src;
  que.push_front(src);
  while (!que.empty()) {
    int u = que.front();
    que.pop_front();
    for (const auto &[v, w1] : g[u]) {
      assert(w1 == 0 || w1 == 1);
      if (dis[v] <= dis[u] + w1) {
        continue;
      }
      dis[v] = dis[u] + w1;
      pre[v] = u;
      if (w1 == 0) {
        que.push_front(v);
      } else {
        que.push_back(v);
      }
    }
  }
  return {dis, pre};
}

struct bellman_ford_result {
  std::vector<int64_t> di1;
  std::vector<int> prv;
  std::vector<bool> neg;
};

/// @brief Return edge ids forming one negative directed cycle anywhere in the
/// graph, in traversal order, or an empty vector when no negative cycle exists.
template <class Weight>
std::vector<int>
find_negative_cycle(int n,
                    const std::vector<std::tuple<int, int, Weight>> &es) {
  assert(n >= 0);
  std::vector<__int128> di1(n);
  std::vector<int> pe(n, -1);
  int cv = -1;
  for (int ite = 0; ite < n; ite++) {
    cv = -1;
    for (int id = 0; id < int(es.size()); id++) {
      auto [u1, to, w1] = es[id];
      assert(0 <= u1 && u1 < n);
      assert(0 <= to && to < n);
      __int128 can = di1[u1] + __int128(w1);
      if (can < di1[to]) {
        di1[to] = can;
        pe[to] = id;
        cv = to;
      }
    }
  }
  if (cv == -1) {
    return {};
  }
  for (int stp = 0; stp < n; stp++) {
    int id = pe[cv];
    assert(id != -1);
    cv = std::get<0>(es[id]);
  }
  int src = cv;
  std::vector<int> cyc;
  do {
    int id = pe[cv];
    assert(id != -1);
    cyc.push_back(id);
    cv = std::get<0>(es[id]);
  } while (cv != src);
  std::reverse(cyc.begin(), cyc.end());
  return cyc;
}

/// @brief Bellman-Ford with propagation from source-reachable negative cycles.
/// A negative-infinite vertex has distance numeric_limits<int64_t>::lowest().
template <class T>
bellman_ford_result bellman_ford(const std::vector<std::vector<T>> &g,
                                 int src) {
  const int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  const int64_t NIF = std::numeric_limits<int64_t>::lowest();
  const __int128 WIF = __int128(1) << 120;
  std::vector<__int128> wd(N, WIF);
  std::vector<int> pre(N, -1);
  std::vector<bool> neg(N);
  wd[src] = 0;
  pre[src] = src;

  for (int ite = 0; ite < N; ite++) {
    bool upd = false;
    for (int u = 0; u < N; u++) {
      if (wd[u] == WIF) {
        continue;
      }
      for (const auto &[v, w1] : g[u]) {
        __int128 can = wd[u] + static_cast<__int128>(w1);
        if (can >= wd[v]) {
          continue;
        }
        wd[v] = can;
        pre[v] = u;
        upd = true;
        if (ite == N - 1) {
          neg[v] = true;
        }
      }
    }
    if (!upd) {
      break;
    }
  }

  std::vector<int> que;
  for (int u = 0; u < N; u++) {
    if (neg[u]) {
      que.push_back(u);
    }
  }
  for (int i = 0; i < int(que.size()); i++) {
    int u = que[i];
    for (const auto &[v, w1] : g[u]) {
      (void)w1;
      if (!neg[v]) {
        neg[v] = true;
        que.push_back(v);
      }
    }
  }

  std::vector<int64_t> dis(N, INF);
  for (int u = 0; u < N; u++) {
    if (neg[u] || wd[u] < __int128(NIF)) {
      dis[u] = NIF;
    } else if (wd[u] < WIF) {
      dis[u] = wd[u] > __int128(INF)
                   ? INF
                   : static_cast<int64_t>(wd[u]);
    }
  }
  return {dis, pre, neg};
}

inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
  std::vector<int> pth;
  int cur = t;
  while (cur != s) {
    assert(cur >= 0);
    pth.push_back(cur);
    cur = pre[cur];
  }
  pth.push_back(s);
  std::reverse(pth.begin(), pth.end());
  return pth;
}

template <class T>
std::vector<std::vector<int64_t>> floyd(std::vector<std::vector<T>> &g) {
  int N = int(g.size());
  const int64_t INF = std::numeric_limits<T>::max() / 2;
  std::vector<std::vector<int64_t>> f(N, std::vector<int64_t>(N, INF));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      f[i][j] = g[i][j];
  for (int i = 0; i < N; i++)
    f[i][i] = 0;
  for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);
  return f;
}

} // namespace noya

#ifndef NOYA_SHORTEST_PATH_HPP
#define NOYA_SHORTEST_PATH_HPP 1

/// @complexity Time: O(V + E) BFS/0-1 BFS, O((V + E) log V) Dijkstra, O(VE) signed-cycle routines.
/// Space: O(V + E).

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

namespace noya {
/// @brief BFS on unweighted graph. @return (distances, predecessors).
inline std::pair<std::vector<int>, std::vector<int>>
bfs_unweighted(std::vector<std::vector<int>> &g, int src) {
  int N = int(g.size());
  const int INF = std::numeric_limits<int>::max();
  std::vector<int> dis(N, INF);
  std::vector<int> pre(N, -1);
  dis[src] = 0;
  pre[src] = src;

  std::vector<int> que{src};
  for (int i = 0; i < int(que.size()); i++) {
    int u = que[i];
    for (auto v : g[u])
      if (dis[v] == INF) {
        dis[v] = dis[u] + 1;
        pre[v] = u;
        que.push_back(v);
      }
  }
  return {dis, pre};
}

/// @brief Dijkstra's algorithm. @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
dijkstra(std::vector<std::vector<T>> &g, int src) {
  int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  std::vector<int64_t> dis(N, INF);
  std::vector<int> pre(N, -1);
  std::priority_queue<std::pair<int64_t, int>,
                      std::vector<std::pair<int64_t, int>>, std::greater<>>
      que;
  que.emplace(dis[src] = 0, src);
  pre[src] = src;
  while (!que.empty()) {
    auto [d, u] = que.top();
    que.pop();
    if (d > dis[u])
      continue;
    for (auto &[v, w] : g[u])
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        pre[v] = u;
        que.emplace(dis[v], v);
      }
  }
  return {dis, pre};
}

/// @brief Shortest paths in a graph whose edge weights are 0 or 1.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
bfs01(const std::vector<std::vector<T>> &g, int src) {
  const int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  std::vector<int64_t> dis(N, INF);
  std::vector<int> pre(N, -1);
  std::deque<int> que;
  dis[src] = 0;
  pre[src] = src;
  que.push_front(src);
  while (!que.empty()) {
    int u = que.front();
    que.pop_front();
    for (const auto &[v, w1] : g[u]) {
      assert(w1 == 0 || w1 == 1);
      if (dis[v] <= dis[u] + w1) {
        continue;
      }
      dis[v] = dis[u] + w1;
      pre[v] = u;
      if (w1 == 0) {
        que.push_front(v);
      } else {
        que.push_back(v);
      }
    }
  }
  return {dis, pre};
}

struct bellman_ford_result {
  std::vector<int64_t> di1;
  std::vector<int> prv;
  std::vector<bool> neg;
};

/// @brief Return edge ids forming one negative directed cycle anywhere in the
/// graph, in traversal order, or an empty vector when no negative cycle exists.
template <class Weight>
std::vector<int>
find_negative_cycle(int n,
                    const std::vector<std::tuple<int, int, Weight>> &es) {
  assert(n >= 0);
  std::vector<__int128> di1(n);
  std::vector<int> pe(n, -1);
  int cv = -1;
  for (int ite = 0; ite < n; ite++) {
    cv = -1;
    for (int id = 0; id < int(es.size()); id++) {
      auto [u1, to, w1] = es[id];
      assert(0 <= u1 && u1 < n);
      assert(0 <= to && to < n);
      __int128 can = di1[u1] + __int128(w1);
      if (can < di1[to]) {
        di1[to] = can;
        pe[to] = id;
        cv = to;
      }
    }
  }
  if (cv == -1) {
    return {};
  }
  for (int stp = 0; stp < n; stp++) {
    int id = pe[cv];
    assert(id != -1);
    cv = std::get<0>(es[id]);
  }
  int src = cv;
  std::vector<int> cyc;
  do {
    int id = pe[cv];
    assert(id != -1);
    cyc.push_back(id);
    cv = std::get<0>(es[id]);
  } while (cv != src);
  std::reverse(cyc.begin(), cyc.end());
  return cyc;
}

/// @brief Bellman-Ford with propagation from source-reachable negative cycles.
/// A negative-infinite vertex has distance numeric_limits<int64_t>::lowest().
template <class T>
bellman_ford_result bellman_ford(const std::vector<std::vector<T>> &g,
                                 int src) {
  const int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  const int64_t NIF = std::numeric_limits<int64_t>::lowest();
  const __int128 WIF = __int128(1) << 120;
  std::vector<__int128> wd(N, WIF);
  std::vector<int> pre(N, -1);
  std::vector<bool> neg(N);
  wd[src] = 0;
  pre[src] = src;

  for (int ite = 0; ite < N; ite++) {
    bool upd = false;
    for (int u = 0; u < N; u++) {
      if (wd[u] == WIF) {
        continue;
      }
      for (const auto &[v, w1] : g[u]) {
        __int128 can = wd[u] + static_cast<__int128>(w1);
        if (can >= wd[v]) {
          continue;
        }
        wd[v] = can;
        pre[v] = u;
        upd = true;
        if (ite == N - 1) {
          neg[v] = true;
        }
      }
    }
    if (!upd) {
      break;
    }
  }

  std::vector<int> que;
  for (int u = 0; u < N; u++) {
    if (neg[u]) {
      que.push_back(u);
    }
  }
  for (int i = 0; i < int(que.size()); i++) {
    int u = que[i];
    for (const auto &[v, w1] : g[u]) {
      (void)w1;
      if (!neg[v]) {
        neg[v] = true;
        que.push_back(v);
      }
    }
  }

  std::vector<int64_t> dis(N, INF);
  for (int u = 0; u < N; u++) {
    if (neg[u] || wd[u] < __int128(NIF)) {
      dis[u] = NIF;
    } else if (wd[u] < WIF) {
      dis[u] = wd[u] > __int128(INF)
                   ? INF
                   : static_cast<int64_t>(wd[u]);
    }
  }
  return {dis, pre, neg};
}

inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
  std::vector<int> pth;
  int cur = t;
  while (cur != s) {
    assert(cur >= 0);
    pth.push_back(cur);
    cur = pre[cur];
  }
  pth.push_back(s);
  std::reverse(pth.begin(), pth.end());
  return pth;
}

template <class T>
std::vector<std::vector<int64_t>> floyd(std::vector<std::vector<T>> &g) {
  int N = int(g.size());
  const int64_t INF = std::numeric_limits<T>::max() / 2;
  std::vector<std::vector<int64_t>> f(N, std::vector<int64_t>(N, INF));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      f[i][j] = g[i][j];
  for (int i = 0; i < N; i++)
    f[i][i] = 0;
  for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);
  return f;
}

} // namespace noya

#endif // NOYA_SHORTEST_PATH_HPP

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

/// @complexity Time: O(V + E) BFS/0-1 BFS, O((V + E) log V) Dijkstra, O(VE) signed-cycle routines.
/// Space: O(V + E).

namespace noya {
/// @brief BFS on unweighted graph. @return (distances, predecessors).
inline std::pair<std::vector<int>, std::vector<int>>
bfs_unweighted(std::vector<std::vector<int>> &g, int src) {
  int N = int(g.size());
  const int INF = std::numeric_limits<int>::max();
  std::vector<int> dis(N, INF);
  std::vector<int> pre(N, -1);
  dis[src] = 0;
  pre[src] = src;

  std::vector<int> que{src};
  for (int i = 0; i < int(que.size()); i++) {
    int u = que[i];
    for (auto v : g[u])
      if (dis[v] == INF) {
        dis[v] = dis[u] + 1;
        pre[v] = u;
        que.push_back(v);
      }
  }
  return {dis, pre};
}

/// @brief Dijkstra's algorithm. @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
dijkstra(std::vector<std::vector<T>> &g, int src) {
  int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  std::vector<int64_t> dis(N, INF);
  std::vector<int> pre(N, -1);
  std::priority_queue<std::pair<int64_t, int>,
                      std::vector<std::pair<int64_t, int>>, std::greater<>>
      que;
  que.emplace(dis[src] = 0, src);
  pre[src] = src;
  while (!que.empty()) {
    auto [d, u] = que.top();
    que.pop();
    if (d > dis[u])
      continue;
    for (auto &[v, w] : g[u])
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        pre[v] = u;
        que.emplace(dis[v], v);
      }
  }
  return {dis, pre};
}

/// @brief Shortest paths in a graph whose edge weights are 0 or 1.
/// @return (distances, predecessors).
template <class T>
std::pair<std::vector<int64_t>, std::vector<int>>
bfs01(const std::vector<std::vector<T>> &g, int src) {
  const int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  std::vector<int64_t> dis(N, INF);
  std::vector<int> pre(N, -1);
  std::deque<int> que;
  dis[src] = 0;
  pre[src] = src;
  que.push_front(src);
  while (!que.empty()) {
    int u = que.front();
    que.pop_front();
    for (const auto &[v, w1] : g[u]) {
      assert(w1 == 0 || w1 == 1);
      if (dis[v] <= dis[u] + w1) {
        continue;
      }
      dis[v] = dis[u] + w1;
      pre[v] = u;
      if (w1 == 0) {
        que.push_front(v);
      } else {
        que.push_back(v);
      }
    }
  }
  return {dis, pre};
}

struct bellman_ford_result {
  std::vector<int64_t> di1;
  std::vector<int> prv;
  std::vector<bool> neg;
};

/// @brief Return edge ids forming one negative directed cycle anywhere in the
/// graph, in traversal order, or an empty vector when no negative cycle exists.
template <class Weight>
std::vector<int>
find_negative_cycle(int n,
                    const std::vector<std::tuple<int, int, Weight>> &es) {
  assert(n >= 0);
  std::vector<__int128> di1(n);
  std::vector<int> pe(n, -1);
  int cv = -1;
  for (int ite = 0; ite < n; ite++) {
    cv = -1;
    for (int id = 0; id < int(es.size()); id++) {
      auto [u1, to, w1] = es[id];
      assert(0 <= u1 && u1 < n);
      assert(0 <= to && to < n);
      __int128 can = di1[u1] + __int128(w1);
      if (can < di1[to]) {
        di1[to] = can;
        pe[to] = id;
        cv = to;
      }
    }
  }
  if (cv == -1) {
    return {};
  }
  for (int stp = 0; stp < n; stp++) {
    int id = pe[cv];
    assert(id != -1);
    cv = std::get<0>(es[id]);
  }
  int src = cv;
  std::vector<int> cyc;
  do {
    int id = pe[cv];
    assert(id != -1);
    cyc.push_back(id);
    cv = std::get<0>(es[id]);
  } while (cv != src);
  std::reverse(cyc.begin(), cyc.end());
  return cyc;
}

/// @brief Bellman-Ford with propagation from source-reachable negative cycles.
/// A negative-infinite vertex has distance numeric_limits<int64_t>::lowest().
template <class T>
bellman_ford_result bellman_ford(const std::vector<std::vector<T>> &g,
                                 int src) {
  const int N = int(g.size());
  const int64_t INF = std::numeric_limits<int64_t>::max();
  const int64_t NIF = std::numeric_limits<int64_t>::lowest();
  const __int128 WIF = __int128(1) << 120;
  std::vector<__int128> wd(N, WIF);
  std::vector<int> pre(N, -1);
  std::vector<bool> neg(N);
  wd[src] = 0;
  pre[src] = src;

  for (int ite = 0; ite < N; ite++) {
    bool upd = false;
    for (int u = 0; u < N; u++) {
      if (wd[u] == WIF) {
        continue;
      }
      for (const auto &[v, w1] : g[u]) {
        __int128 can = wd[u] + static_cast<__int128>(w1);
        if (can >= wd[v]) {
          continue;
        }
        wd[v] = can;
        pre[v] = u;
        upd = true;
        if (ite == N - 1) {
          neg[v] = true;
        }
      }
    }
    if (!upd) {
      break;
    }
  }

  std::vector<int> que;
  for (int u = 0; u < N; u++) {
    if (neg[u]) {
      que.push_back(u);
    }
  }
  for (int i = 0; i < int(que.size()); i++) {
    int u = que[i];
    for (const auto &[v, w1] : g[u]) {
      (void)w1;
      if (!neg[v]) {
        neg[v] = true;
        que.push_back(v);
      }
    }
  }

  std::vector<int64_t> dis(N, INF);
  for (int u = 0; u < N; u++) {
    if (neg[u] || wd[u] < __int128(NIF)) {
      dis[u] = NIF;
    } else if (wd[u] < WIF) {
      dis[u] = wd[u] > __int128(INF)
                   ? INF
                   : static_cast<int64_t>(wd[u]);
    }
  }
  return {dis, pre, neg};
}

inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
  std::vector<int> pth;
  int cur = t;
  while (cur != s) {
    assert(cur >= 0);
    pth.push_back(cur);
    cur = pre[cur];
  }
  pth.push_back(s);
  std::reverse(pth.begin(), pth.end());
  return pth;
}

template <class T>
std::vector<std::vector<int64_t>> floyd(std::vector<std::vector<T>> &g) {
  int N = int(g.size());
  const int64_t INF = std::numeric_limits<T>::max() / 2;
  std::vector<std::vector<int64_t>> f(N, std::vector<int64_t>(N, INF));
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      f[i][j] = g[i][j];
  for (int i = 0; i < N; i++)
    f[i][i] = 0;
  for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);
  return f;
}

} // namespace noya