k_shortest_walk.hpp¶
Return the lengths of the first k source-to-target directed walks. Reverse Dijkstra fixes one shortest-path tree toward the target. Every non-tree edge has a nonnegative sidetrack cost weight+dist[to]-dist[from]; a walk is its shortest base path plus an ordered sequence of sidetracks. Persistent leftist heaps collect all sidetracks available along each tree path. A final priority queue explores replacing a chosen sidetrack by a heap child or appending one after its destination, so walks are emitted in nondecreasing total length. Vertices and edges may repeat, including through zero-weight cycles.
Verified by k_shortest_walk.
按长度顺序求源点到终点的前 k 条游走，允许重复经过顶点和边。
Implementation¶
#ifndef NOYA_K_SHORTEST_WALK_HPP
#define NOYA_K_SHORTEST_WALK_HPP 1
/// @complexity Time: O((V + E) log V + k log k).
/// Space: O(V + E log V + k).
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
namespace k_shortest_walk_internal {
template <class Weight> struct persistent_leftist_heap {
struct node {
Weight value{};
int destination = -1;
int left = -1;
int right = -1;
int rank = 1;
};
std::vector<node> nodes;
int node_rank(int id) const { return id == -1 ? 0 : nodes[id].rank; }
int meld(int first, int second) {
if (first == -1 || second == -1) {
return first == -1 ? second : first;
}
if (nodes[second].value < nodes[first].value) {
std::swap(first, second);
}
node copy = nodes[first];
copy.right = meld(copy.right, second);
if (node_rank(copy.left) < node_rank(copy.right)) {
std::swap(copy.left, copy.right);
}
copy.rank = node_rank(copy.right) + 1;
nodes.push_back(copy);
return int(nodes.size()) - 1;
}
int insert(int root, Weight value, int destination) {
nodes.push_back(node{value, destination});
return meld(root, int(nodes.size()) - 1);
}
};
} // namespace k_shortest_walk_internal
/// @brief Return the lengths of the first k source-to-target directed walks.
/// Reverse Dijkstra fixes one shortest-path tree toward the target. Every
/// non-tree edge has a nonnegative sidetrack cost
/// `weight+dist[to]-dist[from]`; a walk is its shortest base path plus an
/// ordered sequence of sidetracks. Persistent leftist heaps collect all
/// sidetracks available along each tree path. A final priority queue explores
/// replacing a chosen sidetrack by a heap child or appending one after its
/// destination, so walks are emitted in nondecreasing total length. Vertices
/// and edges may repeat, including through zero-weight cycles.
template <class Weight>
std::vector<Weight> k_shortest_walk_lengths(
int vertex_count,
const std::vector<std::tuple<int, int, Weight>> &edges, int source,
int target, int count) {
assert(vertex_count >= 0);
assert(0 <= source && source < vertex_count);
assert(0 <= target && target < vertex_count);
assert(count >= 0);
if (count == 0) {
return {};
}
struct adjacent_edge {
int vertex;
Weight weight;
int id;
};
std::vector<std::vector<adjacent_edge>> outgoing(vertex_count);
std::vector<std::vector<adjacent_edge>> reversed(vertex_count);
for (int id = 0; id < int(edges.size()); id++) {
auto [from, to, weight] = edges[id];
assert(0 <= from && from < vertex_count);
assert(0 <= to && to < vertex_count);
assert(weight >= Weight{});
outgoing[from].push_back({to, weight, id});
reversed[to].push_back({from, weight, id});
}
const Weight infinity = std::numeric_limits<Weight>::max() / 4;
std::vector<Weight> distance(vertex_count, infinity);
std::vector<int> tree_edge(vertex_count, -1);
std::vector<int> tree_parent(vertex_count, -1);
using distance_entry = std::pair<Weight, int>;
std::priority_queue<distance_entry, std::vector<distance_entry>,
std::greater<distance_entry>>
dijkstra_queue;
distance[target] = Weight{};
dijkstra_queue.emplace(Weight{}, target);
while (!dijkstra_queue.empty()) {
auto [current_distance, vertex] = dijkstra_queue.top();
dijkstra_queue.pop();
if (current_distance != distance[vertex]) {
continue;
}
for (auto [predecessor, weight, id] : reversed[vertex]) {
Weight candidate = current_distance + weight;
if (candidate < distance[predecessor]) {
distance[predecessor] = candidate;
tree_parent[predecessor] = vertex;
tree_edge[predecessor] = id;
dijkstra_queue.emplace(candidate, predecessor);
}
}
}
if (distance[source] == infinity) {
return {};
}
std::vector<std::vector<int>> tree_children(vertex_count);
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (tree_parent[vertex] != -1) {
tree_children[tree_parent[vertex]].push_back(vertex);
}
}
using heap_type =
k_shortest_walk_internal::persistent_leftist_heap<Weight>;
heap_type heap;
std::vector<int> heap_root(vertex_count, -1);
std::vector<int> traversal{target};
for (int index = 0; index < int(traversal.size()); index++) {
int vertex = traversal[index];
if (tree_parent[vertex] != -1) {
heap_root[vertex] = heap_root[tree_parent[vertex]];
}
for (auto [to, weight, id] : outgoing[vertex]) {
if (id == tree_edge[vertex] || distance[to] == infinity) {
continue;
}
Weight sidetrack = weight + distance[to] - distance[vertex];
heap_root[vertex] = heap.insert(heap_root[vertex], sidetrack, to);
}
traversal.insert(traversal.end(), tree_children[vertex].begin(),
tree_children[vertex].end());
}
using candidate = std::pair<Weight, int>;
std::priority_queue<candidate, std::vector<candidate>,
std::greater<candidate>>
candidates;
candidates.emplace(distance[source], -1);
std::vector<Weight> result;
result.reserve(count);
while (!candidates.empty() && int(result.size()) < count) {
auto [total, node_id] = candidates.top();
candidates.pop();
result.push_back(total);
int continuation_root;
if (node_id == -1) {
continuation_root = heap_root[source];
} else {
const auto ¤t = heap.nodes[node_id];
for (int child : {current.left, current.right}) {
if (child != -1) {
candidates.emplace(total + heap.nodes[child].value - current.value,
child);
}
}
continuation_root = heap_root[current.destination];
}
if (continuation_root != -1) {
candidates.emplace(total + heap.nodes[continuation_root].value,
continuation_root);
}
}
return result;
}
} // namespace noya
#endif // NOYA_K_SHORTEST_WALK_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
/// @complexity Time: O((V + E) log V + k log k).
/// Space: O(V + E log V + k).
namespace noya {
namespace k_shortest_walk_internal {
template <class Weight> struct persistent_leftist_heap {
struct node {
Weight value{};
int destination = -1;
int left = -1;
int right = -1;
int rank = 1;
};
std::vector<node> nodes;
int node_rank(int id) const { return id == -1 ? 0 : nodes[id].rank; }
int meld(int first, int second) {
if (first == -1 || second == -1) {
return first == -1 ? second : first;
}
if (nodes[second].value < nodes[first].value) {
std::swap(first, second);
}
node copy = nodes[first];
copy.right = meld(copy.right, second);
if (node_rank(copy.left) < node_rank(copy.right)) {
std::swap(copy.left, copy.right);
}
copy.rank = node_rank(copy.right) + 1;
nodes.push_back(copy);
return int(nodes.size()) - 1;
}
int insert(int root, Weight value, int destination) {
nodes.push_back(node{value, destination});
return meld(root, int(nodes.size()) - 1);
}
};
} // namespace k_shortest_walk_internal
/// @brief Return the lengths of the first k source-to-target directed walks.
/// Reverse Dijkstra fixes one shortest-path tree toward the target. Every
/// non-tree edge has a nonnegative sidetrack cost
/// `weight+dist[to]-dist[from]`; a walk is its shortest base path plus an
/// ordered sequence of sidetracks. Persistent leftist heaps collect all
/// sidetracks available along each tree path. A final priority queue explores
/// replacing a chosen sidetrack by a heap child or appending one after its
/// destination, so walks are emitted in nondecreasing total length. Vertices
/// and edges may repeat, including through zero-weight cycles.
template <class Weight>
std::vector<Weight> k_shortest_walk_lengths(
int vertex_count,
const std::vector<std::tuple<int, int, Weight>> &edges, int source,
int target, int count) {
assert(vertex_count >= 0);
assert(0 <= source && source < vertex_count);
assert(0 <= target && target < vertex_count);
assert(count >= 0);
if (count == 0) {
return {};
}
struct adjacent_edge {
int vertex;
Weight weight;
int id;
};
std::vector<std::vector<adjacent_edge>> outgoing(vertex_count);
std::vector<std::vector<adjacent_edge>> reversed(vertex_count);
for (int id = 0; id < int(edges.size()); id++) {
auto [from, to, weight] = edges[id];
assert(0 <= from && from < vertex_count);
assert(0 <= to && to < vertex_count);
assert(weight >= Weight{});
outgoing[from].push_back({to, weight, id});
reversed[to].push_back({from, weight, id});
}
const Weight infinity = std::numeric_limits<Weight>::max() / 4;
std::vector<Weight> distance(vertex_count, infinity);
std::vector<int> tree_edge(vertex_count, -1);
std::vector<int> tree_parent(vertex_count, -1);
using distance_entry = std::pair<Weight, int>;
std::priority_queue<distance_entry, std::vector<distance_entry>,
std::greater<distance_entry>>
dijkstra_queue;
distance[target] = Weight{};
dijkstra_queue.emplace(Weight{}, target);
while (!dijkstra_queue.empty()) {
auto [current_distance, vertex] = dijkstra_queue.top();
dijkstra_queue.pop();
if (current_distance != distance[vertex]) {
continue;
}
for (auto [predecessor, weight, id] : reversed[vertex]) {
Weight candidate = current_distance + weight;
if (candidate < distance[predecessor]) {
distance[predecessor] = candidate;
tree_parent[predecessor] = vertex;
tree_edge[predecessor] = id;
dijkstra_queue.emplace(candidate, predecessor);
}
}
}
if (distance[source] == infinity) {
return {};
}
std::vector<std::vector<int>> tree_children(vertex_count);
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (tree_parent[vertex] != -1) {
tree_children[tree_parent[vertex]].push_back(vertex);
}
}
using heap_type =
k_shortest_walk_internal::persistent_leftist_heap<Weight>;
heap_type heap;
std::vector<int> heap_root(vertex_count, -1);
std::vector<int> traversal{target};
for (int index = 0; index < int(traversal.size()); index++) {
int vertex = traversal[index];
if (tree_parent[vertex] != -1) {
heap_root[vertex] = heap_root[tree_parent[vertex]];
}
for (auto [to, weight, id] : outgoing[vertex]) {
if (id == tree_edge[vertex] || distance[to] == infinity) {
continue;
}
Weight sidetrack = weight + distance[to] - distance[vertex];
heap_root[vertex] = heap.insert(heap_root[vertex], sidetrack, to);
}
traversal.insert(traversal.end(), tree_children[vertex].begin(),
tree_children[vertex].end());
}
using candidate = std::pair<Weight, int>;
std::priority_queue<candidate, std::vector<candidate>,
std::greater<candidate>>
candidates;
candidates.emplace(distance[source], -1);
std::vector<Weight> result;
result.reserve(count);
while (!candidates.empty() && int(result.size()) < count) {
auto [total, node_id] = candidates.top();
candidates.pop();
result.push_back(total);
int continuation_root;
if (node_id == -1) {
continuation_root = heap_root[source];
} else {
const auto ¤t = heap.nodes[node_id];
for (int child : {current.left, current.right}) {
if (child != -1) {
candidates.emplace(total + heap.nodes[child].value - current.value,
child);
}
}
continuation_root = heap_root[current.destination];
}
if (continuation_root != -1) {
candidates.emplace(total + heap.nodes[continuation_root].value,
continuation_root);
}
}
return result;
}
} // namespace noya