shortest_path.hpp¶
Shortest-path routines for unweighted, 0/1-weighted, nonnegative, and signed-weight graphs.
Verified by shortest_path.
统一提供 BFS、01-BFS、Dijkstra 与 Bellman-Ford；按边权范围求单源最短路并恢复路径。
Implementation¶
#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 start) {
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[start] = 0;
pre[start] = start;
std::vector<int> que{start};
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 start) {
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[start] = 0, start);
pre[start] = start;
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 start) {
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[start] = 0;
pre[start] = start;
que.push_front(start);
while (!que.empty()) {
int u = que.front();
que.pop_front();
for (const auto &[v, weight] : g[u]) {
assert(weight == 0 || weight == 1);
if (dis[v] <= dis[u] + weight) {
continue;
}
dis[v] = dis[u] + weight;
pre[v] = u;
if (weight == 0) {
que.push_front(v);
} else {
que.push_back(v);
}
}
}
return {dis, pre};
}
struct bellman_ford_result {
std::vector<int64_t> distance;
std::vector<int> predecessor;
std::vector<bool> negative_infinite;
};
/// @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>> &edges) {
assert(n >= 0);
std::vector<__int128> distance(n);
std::vector<int> predecessor_edge(n, -1);
int changed_vertex = -1;
for (int iteration = 0; iteration < n; iteration++) {
changed_vertex = -1;
for (int id = 0; id < int(edges.size()); id++) {
auto [from, to, weight] = edges[id];
assert(0 <= from && from < n);
assert(0 <= to && to < n);
__int128 candidate = distance[from] + __int128(weight);
if (candidate < distance[to]) {
distance[to] = candidate;
predecessor_edge[to] = id;
changed_vertex = to;
}
}
}
if (changed_vertex == -1) {
return {};
}
for (int step = 0; step < n; step++) {
int id = predecessor_edge[changed_vertex];
assert(id != -1);
changed_vertex = std::get<0>(edges[id]);
}
int start = changed_vertex;
std::vector<int> cycle;
do {
int id = predecessor_edge[changed_vertex];
assert(id != -1);
cycle.push_back(id);
changed_vertex = std::get<0>(edges[id]);
} while (changed_vertex != start);
std::reverse(cycle.begin(), cycle.end());
return cycle;
}
/// @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 start) {
const int N = int(g.size());
const int64_t INF = std::numeric_limits<int64_t>::max();
const int64_t NEG_INF = std::numeric_limits<int64_t>::lowest();
const __int128 WIDE_INF = __int128(1) << 120;
std::vector<__int128> wide_distance(N, WIDE_INF);
std::vector<int> pre(N, -1);
std::vector<bool> negative_infinite(N);
wide_distance[start] = 0;
pre[start] = start;
for (int iteration = 0; iteration < N; iteration++) {
bool updated = false;
for (int u = 0; u < N; u++) {
if (wide_distance[u] == WIDE_INF) {
continue;
}
for (const auto &[v, weight] : g[u]) {
__int128 candidate = wide_distance[u] + static_cast<__int128>(weight);
if (candidate >= wide_distance[v]) {
continue;
}
wide_distance[v] = candidate;
pre[v] = u;
updated = true;
if (iteration == N - 1) {
negative_infinite[v] = true;
}
}
}
if (!updated) {
break;
}
}
std::vector<int> que;
for (int u = 0; u < N; u++) {
if (negative_infinite[u]) {
que.push_back(u);
}
}
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (const auto &[v, weight] : g[u]) {
(void)weight;
if (!negative_infinite[v]) {
negative_infinite[v] = true;
que.push_back(v);
}
}
}
std::vector<int64_t> dis(N, INF);
for (int u = 0; u < N; u++) {
if (negative_infinite[u] || wide_distance[u] < __int128(NEG_INF)) {
dis[u] = NEG_INF;
} else if (wide_distance[u] < WIDE_INF) {
dis[u] = wide_distance[u] > __int128(INF)
? INF
: static_cast<int64_t>(wide_distance[u]);
}
}
return {dis, pre, negative_infinite};
}
inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
std::vector<int> path;
int cur = t;
while (cur != s) {
assert(cur >= 0);
path.push_back(cur);
cur = pre[cur];
}
path.push_back(s);
std::reverse(path.begin(), path.end());
return path;
}
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 start) {
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[start] = 0;
pre[start] = start;
std::vector<int> que{start};
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 start) {
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[start] = 0, start);
pre[start] = start;
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 start) {
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[start] = 0;
pre[start] = start;
que.push_front(start);
while (!que.empty()) {
int u = que.front();
que.pop_front();
for (const auto &[v, weight] : g[u]) {
assert(weight == 0 || weight == 1);
if (dis[v] <= dis[u] + weight) {
continue;
}
dis[v] = dis[u] + weight;
pre[v] = u;
if (weight == 0) {
que.push_front(v);
} else {
que.push_back(v);
}
}
}
return {dis, pre};
}
struct bellman_ford_result {
std::vector<int64_t> distance;
std::vector<int> predecessor;
std::vector<bool> negative_infinite;
};
/// @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>> &edges) {
assert(n >= 0);
std::vector<__int128> distance(n);
std::vector<int> predecessor_edge(n, -1);
int changed_vertex = -1;
for (int iteration = 0; iteration < n; iteration++) {
changed_vertex = -1;
for (int id = 0; id < int(edges.size()); id++) {
auto [from, to, weight] = edges[id];
assert(0 <= from && from < n);
assert(0 <= to && to < n);
__int128 candidate = distance[from] + __int128(weight);
if (candidate < distance[to]) {
distance[to] = candidate;
predecessor_edge[to] = id;
changed_vertex = to;
}
}
}
if (changed_vertex == -1) {
return {};
}
for (int step = 0; step < n; step++) {
int id = predecessor_edge[changed_vertex];
assert(id != -1);
changed_vertex = std::get<0>(edges[id]);
}
int start = changed_vertex;
std::vector<int> cycle;
do {
int id = predecessor_edge[changed_vertex];
assert(id != -1);
cycle.push_back(id);
changed_vertex = std::get<0>(edges[id]);
} while (changed_vertex != start);
std::reverse(cycle.begin(), cycle.end());
return cycle;
}
/// @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 start) {
const int N = int(g.size());
const int64_t INF = std::numeric_limits<int64_t>::max();
const int64_t NEG_INF = std::numeric_limits<int64_t>::lowest();
const __int128 WIDE_INF = __int128(1) << 120;
std::vector<__int128> wide_distance(N, WIDE_INF);
std::vector<int> pre(N, -1);
std::vector<bool> negative_infinite(N);
wide_distance[start] = 0;
pre[start] = start;
for (int iteration = 0; iteration < N; iteration++) {
bool updated = false;
for (int u = 0; u < N; u++) {
if (wide_distance[u] == WIDE_INF) {
continue;
}
for (const auto &[v, weight] : g[u]) {
__int128 candidate = wide_distance[u] + static_cast<__int128>(weight);
if (candidate >= wide_distance[v]) {
continue;
}
wide_distance[v] = candidate;
pre[v] = u;
updated = true;
if (iteration == N - 1) {
negative_infinite[v] = true;
}
}
}
if (!updated) {
break;
}
}
std::vector<int> que;
for (int u = 0; u < N; u++) {
if (negative_infinite[u]) {
que.push_back(u);
}
}
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (const auto &[v, weight] : g[u]) {
(void)weight;
if (!negative_infinite[v]) {
negative_infinite[v] = true;
que.push_back(v);
}
}
}
std::vector<int64_t> dis(N, INF);
for (int u = 0; u < N; u++) {
if (negative_infinite[u] || wide_distance[u] < __int128(NEG_INF)) {
dis[u] = NEG_INF;
} else if (wide_distance[u] < WIDE_INF) {
dis[u] = wide_distance[u] > __int128(INF)
? INF
: static_cast<int64_t>(wide_distance[u]);
}
}
return {dis, pre, negative_infinite};
}
inline std::vector<int> find_path(std::vector<int> &pre, int s, int t) {
std::vector<int> path;
int cur = t;
while (cur != s) {
assert(cur >= 0);
path.push_back(cur);
cur = pre[cur];
}
path.push_back(s);
std::reverse(path.begin(), path.end());
return path;
}
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