Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
k_shortest_paths.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Algorithms to compute k-shortest paths. Currently, only Yen's algorithm is
15// implemented.
16//
17// TODO(user): implement Lawler's modification:
18// https://pubsonline.informs.org/doi/abs/10.1287/mnsc.18.7.401
19//
20// | Algo. | Neg. weights | Neg.-weight loops | Graph type | Loopless paths |
21// |-------|--------------|-------------------|--------------|----------------|
22// | Yen | No | No | (Un)directed | Yes |
23//
24//
25// Loopless path: path not going through the same node more than once. Also
26// called simple path.
27//
28// The implementations do not support multigraphs, i.e. graphs with several
29// arcs between the same source and destination nodes. One way to work around
30// this limitation is to create dummy nodes between the source and destination
31// nodes, with one of the edges carrying the weight and the other having a zero
32// weight. This transformation slightly increases the size of the graph.
33// If you have n edges between the nodes s and t, with the weights w_i, do the
34// following: create n - 1 nodes (d_i for i from 2 to n), create n - 1 edges
35// between s and d_i with weight w_i, create n - 1 edges between d_i and t with
36// weight 0.
37//
38//
39// Design choices
40// ==============
41//
42// The design takes some inspiration from `shortest_paths.h` and
43// `bounded_dijkstra.h`, but the shortest-path and k-shortest-path problems have
44// vastly different structures.
45// For instance, a path container that only stores distances, like
46// `DistanceContainer` in `shortest_paths.h`, is irrelevant as an output for
47// this problem: it can only characterize one path, the shortest one.
48// This is why the results are stored in an intermediate structure, containing
49// the paths (as a sequence of nodes, just like `PathContainerImpl` subclasses)
50// and their distance.
51//
52// Only the one-to-one k-shortest-path problem is well-defined. Variants with
53// multiple sources and/or destinations pose representational challenges whose
54// solution is likely to be algorithm-dependent.
55// Optimizations of path storage such as `PathTree` are not general enough to
56// store k shortest paths: the set of paths for a given index for many
57// sources/destinations is not ensured to form a set for each index. (While the
58// first paths will form such a tree, storing *different* second paths for each
59// source-destination pair may be impossible to do in a tree.)
60//
61// Unlike the functions in `shortest_paths.h`, the functions in this file
62// directly return their result, to follow the current best practices.
63
64#ifndef OR_TOOLS_GRAPH_K_SHORTEST_PATHS_H_
65#define OR_TOOLS_GRAPH_K_SHORTEST_PATHS_H_
66
67#include <algorithm>
68#include <functional>
69#include <iterator>
70#include <limits>
71#include <queue>
72#include <tuple>
73#include <utility>
74#include <vector>
75
76#include "absl/algorithm/container.h"
77#include "absl/base/optimization.h"
78#include "absl/container/flat_hash_set.h"
79#include "absl/log/check.h"
80#include "absl/log/log.h"
81#include "absl/strings/str_join.h"
82#include "absl/types/span.h"
85
86namespace operations_research {
87
88// Stores the solution to a k-shortest path problem. `paths` contains up to `k`
89// paths from `source` to `destination` (these nodes are arguments to the
90// algorithm), each having a distance stored in `distances`.
91//
92// The paths in `paths` start with `origin` and end at `destination`.
93//
94// If the computations are unsuccessful for any reason, the vectors are empty.
95template <class GraphType>
96struct KShortestPaths {
97 // The paths are stored as vectors of nodes, like the other graph algorithms.
98 // TODO(user): what about vectors of arcs? That might be faster
99 // (potentially, add a function to transform it into a vector of nodes if the
100 // user really needs it). It would also have the nice benefit of removing the
101 // need for `distances` (compute it on the fly), with a reference to the graph
102 // and the costs.
103 std::vector<std::vector<typename GraphType::NodeIndex>> paths;
104 std::vector<PathDistance> distances;
106
107// Computes up to k shortest paths from the node `source` to the node
108// `destination` in the given directed `graph`. The paths are guaranteed not to
109// have loops.
110//
111// Hypotheses on input (which are not checked at runtime):
112// - No multigraphs (more than one edge or a pair of nodes). The behavior is
113// undefined otherwise.
114// - The `arc_lengths` are supposed to be nonnegative. The behavior is
115// undefined otherwise.
116// TODO(user): relax to "no negative-weight cycles" (no Dijkstra).
117// - The graphs might have loops.
118//
119// This function uses Yen's algorithm, which guarantees to find the first k
120// shortest paths in O(k n (m + n log n)) for n nodes and m edges. This
121// algorithm is an implementation of the idea of detours.
122//
123// Yen, Jin Y. "Finding the k Shortest Loopless Paths in a Network". Management
124// Science. 17 (11): 712–716, 1971.
125// https://doi.org/10.1287%2Fmnsc.17.11.712
126template <class GraphType>
128 const GraphType& graph, const std::vector<PathDistance>& arc_lengths,
129 typename GraphType::NodeIndex source,
130 typename GraphType::NodeIndex destination, unsigned k);
131
132// End of the interface. Below is the implementation.
133
134// TODO(user): introduce an enum to choose the algorithm. It's useless as
135// long as this file only provides Yen.
136
137namespace internal {
138
139const PathDistance kMaxDistance = std::numeric_limits<PathDistance>::max() - 1;
141 std::numeric_limits<PathDistance>::max();
142
143// Determines the arc index from a source to a destination.
144//
145// This operation requires iterating through the set of outgoing arcs from the
146// source node, which might be expensive.
147//
148// In a multigraph, this function returns an index for one of the edges between
149// the source and the destination.
150template <class GraphType>
151typename GraphType::ArcIndex FindArcIndex(
152 const GraphType& graph, const typename GraphType::NodeIndex source,
153 const typename GraphType::NodeIndex destination) {
154 const auto outgoing_arcs_iter = graph.OutgoingArcs(source);
155 const auto arc = std::find_if(
156 outgoing_arcs_iter.begin(), outgoing_arcs_iter.end(),
157 [&graph, destination](const typename GraphType::ArcIndex arc) {
158 return graph.Head(arc) == destination;
159 });
160 return (arc != outgoing_arcs_iter.end()) ? *arc : GraphType::kNilArc;
161}
162
163// Determines the shortest path from the given source and destination, returns a
164// tuple with the path (as a vector of node indices) and its cost.
165template <class GraphType>
166std::tuple<std::vector<typename GraphType::NodeIndex>, PathDistance>
167ComputeShortestPath(const GraphType& graph,
168 const std::vector<PathDistance>& arc_lengths,
169 const typename GraphType::NodeIndex source,
170 const typename GraphType::NodeIndex destination) {
172 &arc_lengths);
173 dijkstra.RunBoundedDijkstra(source, kMaxDistance);
174 const PathDistance path_length = dijkstra.distances()[destination];
175
176 if (path_length >= kMaxDistance) {
177 // There are shortest paths in this graph, just not from the source to this
178 // destination.
179 // This case only happens when some arcs have an infinite length (i.e.
180 // larger than `kMaxDistance`): `BoundedDijkstraWrapper::NodePathTo` fails
181 // to return a path, even empty.
182 return {std::vector<typename GraphType::NodeIndex>{},
184 }
185
186 if (std::vector<typename GraphType::NodeIndex> path =
187 std::move(dijkstra.NodePathTo(destination));
188 !path.empty()) {
189 return {std::move(path), path_length};
190 } else {
191 return {std::vector<typename GraphType::NodeIndex>{},
193 }
194}
195
196// Computes the total length of a path.
197template <class GraphType>
199 const GraphType& graph, const absl::Span<const PathDistance> arc_lengths,
200 const absl::Span<const typename GraphType::NodeIndex> path) {
201 PathDistance distance = 0;
202 for (typename GraphType::NodeIndex i = 0; i < path.size() - 1; ++i) {
203 const typename GraphType::ArcIndex arc =
204 internal::FindArcIndex(graph, path[i], path[i + 1]);
205 DCHECK_NE(arc, GraphType::kNilArc);
206 distance += arc_lengths[arc];
207 }
208 return distance;
209}
210
211// Stores a path with a priority (typically, the distance), with a comparison
212// operator that operates on the priority.
213template <class GraphType>
214class PathWithPriority {
215 public:
216 using NodeIndex = typename GraphType::NodeIndex;
218 PathWithPriority(PathDistance priority, std::vector<NodeIndex> path)
219 : path_(std::move(path)), priority_(priority) {}
220 bool operator>(const PathWithPriority& other) const {
221 return priority_ > other.priority_;
222 }
223
224 [[nodiscard]] const std::vector<NodeIndex>& path() const { return path_; }
225 [[nodiscard]] PathDistance priority() const { return priority_; }
227 private:
228 std::vector<NodeIndex> path_;
229 PathDistance priority_;
230};
231
232// Container adapter to be used with STL container adapters such as
233// std::priority_queue. It gives access to the underlying container, which is a
234// protected member in a standard STL container adapter.
235template <class Container>
236class UnderlyingContainerAdapter : public Container {
237 public:
238 typedef typename Container::container_type container_type;
239 // No mutable version of `container`, so that the user cannot change the data
240 // within the container: they might destroy the container's invariants.
241 [[nodiscard]] const container_type& container() const { return this->c; }
243
244} // namespace internal
245
246// TODO(user): Yen's algorithm can work with negative weights, but
247// Dijkstra cannot.
248//
249// Yen, Jin Y. "Finding the k Shortest Loopless Paths in a Network". Management
250// Science. 17 (11): 712–716, 1971.
251// https://doi.org/10.1287%2Fmnsc.17.11.712
252//
253// Yen's notations:
254// - Source node: (1).
255// - Destination node: (N).
256// - Path from (1) to (j): (1) - (i) - ... - (j).
257// - Cost for following the arc from (i) to (j), potentially negative: d_ij.
258// - k-th shortest path: A^k == (1) - (2^k) - (3^k) - ... - (Q_k^k) - (N).
259// - Deviation from A^k-1 at (i): A_i^k. This is the shortest path from (1) to
260// (N) that is identical to A^k-1 from (1) to (i^k-1), then different from all
261// the first k-1 shortest paths {A^1, A^2, ..., A^k-1}.
262// - Root of A_i^k: R_i^k. This is the first subpath of A_i^k that coincides
263// with A^k-1, i.e. A_i^k until i^k-1.
264// - Spur of A_i^k: S_i^k. This is the last subpart of A_i^k with only one node
265// coinciding with A_i^k, (i^k-1), i.e. A_i^k from i^k-1 onwards.
266//
267// Example graph, paths from A to H (more classical notations):
268// C - D
269// / / \
270// A - B / G - H
271// \ / /
272// E - F
273// Source node: A. Destination node: H.
274// Three paths from A to H, say they are ordered from the cheapest to the most
275// expensive:
276// - 1st path: A - B - C - D - G - H
277// - 2nd path: A - B - E - F - G - H
278// - 3rd path: A - B - E - D - G - H
279// To start with, Yen's algorithm uses the shortest path:
280// A^1 = A - B - C - D - G - H
281// To compute the second path A^2, compute a detour around A^1. Consider the
282// iteration where B is the spur node.
283// - Spur node: 2^1 = B.
284// - Root of A^1_2: R_1^2 = A - B (including the spur node 2^1 = B).
285// - Spur path S_1^2 starts at the spur node 2^1 = B. There are two possible
286// spur paths, the cheapest being:
287// S_1^2 = B - E - F - G - H
288template <class GraphType>
290 const GraphType& graph, const std::vector<PathDistance>& arc_lengths,
291 typename GraphType::NodeIndex source,
292 typename GraphType::NodeIndex destination, unsigned k) {
293 using NodeIndex = typename GraphType::NodeIndex;
294
296
297 CHECK_GE(k, 0) << "k must be nonnegative. Input value: " << k;
298 CHECK_NE(k, 0) << "k cannot be zero: you are requesting zero paths!";
299
300 CHECK_GT(graph.num_nodes(), 0) << "The graph is empty: it has no nodes";
301 CHECK_GT(graph.num_arcs(), 0) << "The graph is empty: it has no arcs";
302
303 CHECK_GE(source, 0) << "The source node must be nonnegative. Input value: "
304 << source;
305 CHECK_LT(source, graph.num_nodes())
306 << "The source node must be a valid node. Input value: " << source
307 << ". Number of nodes in the input graph: " << graph.num_nodes();
308 CHECK_GE(destination, 0)
309 << "The source node must be nonnegative. Input value: " << destination;
310 CHECK_LT(destination, graph.num_nodes())
311 << "The destination node must be a valid node. Input value: "
312 << destination
313 << ". Number of nodes in the input graph: " << graph.num_nodes();
314
316
317 // First step: compute the shortest path.
318 {
319 std::tuple<std::vector<NodeIndex>, PathDistance> first_path =
320 internal::ComputeShortestPath(graph, arc_lengths, source, destination);
321 if (std::get<0>(first_path).empty()) return paths;
322 paths.paths.push_back(std::move(std::get<0>(first_path)));
323 paths.distances.push_back(std::get<1>(first_path));
324 }
325
326 if (k == 1) {
327 return paths;
328 }
329
330 // Generate variant paths.
332 std::priority_queue<internal::PathWithPriority<GraphType>,
333 std::vector<internal::PathWithPriority<GraphType>>,
334 std::greater<internal::PathWithPriority<GraphType>>>>
335 variant_path_queue;
336
337 // One path has already been generated (the shortest one). Only k-1 more
338 // paths need to be generated.
339 for (; k > 1; --k) {
340 VLOG(1) << "k: " << k;
341
342 // Generate variant paths from the last shortest path.
343 const absl::Span<NodeIndex> last_shortest_path =
344 absl::MakeSpan(paths.paths.back());
345
346 // TODO(user): think about adding parallelism for this loop to improve
347 // running times. This is not a priority as long as the algorithm is
348 // faster than the one in `shortest_paths.h`.
349 for (int spur_node_position = 0;
350 spur_node_position < last_shortest_path.size() - 1;
351 ++spur_node_position) {
352 VLOG(4) << " spur_node_position: " << spur_node_position;
353 VLOG(4) << " last_shortest_path: "
354 << absl::StrJoin(last_shortest_path, " - ") << " ("
355 << last_shortest_path.size() << ")";
356 if (spur_node_position > 0) {
357 DCHECK_NE(last_shortest_path[spur_node_position], source);
358 }
359 DCHECK_NE(last_shortest_path[spur_node_position], destination);
360
361 const NodeIndex spur_node = last_shortest_path[spur_node_position];
362 // Consider the part of the last shortest path up to and excluding the
363 // spur node. If spur_node_position == 0, this span only contains the
364 // source node.
365 const absl::Span<NodeIndex> root_path =
366 last_shortest_path.subspan(0, spur_node_position + 1);
367 DCHECK_GE(root_path.length(), 1);
368 DCHECK_NE(root_path.back(), destination);
369
370 // Simplify the graph to have different paths using infinite lengths:
371 // copy the weights, set some of them to infinity. There is no need to
372 // restore the graph to its previous state in this case.
373 //
374 // This trick is used in the original article (it's old-fashioned), but
375 // not in Wikipedia's pseudocode (it prefers mutating the graph, which is
376 // harder to do without copying the whole graph structure).
377 // Copying the whole graph might be quite expensive, especially as it is
378 // not useful for long (computing one shortest path).
379 std::vector<PathDistance> arc_lengths_for_detour = arc_lengths;
380 for (absl::Span<const NodeIndex> previous_path : paths.paths) {
381 // Check among the previous paths: if part of the path coincides with
382 // the first few nodes up to the spur node (included), forbid this part
383 // of the path in the search for the next shortest path. More
384 // precisely, in that case, avoid the arc from the spur node to the
385 // next node in the path.
386 if (previous_path.size() <= root_path.length()) continue;
387 const bool has_same_prefix_as_root_path = std::equal(
388 root_path.begin(), root_path.end(), previous_path.begin(),
389 previous_path.begin() + root_path.length());
390 if (!has_same_prefix_as_root_path) continue;
391
392 const typename GraphType::ArcIndex after_spur_node_arc =
393 internal::FindArcIndex(graph, previous_path[spur_node_position],
394 previous_path[spur_node_position + 1]);
395 VLOG(4) << " after_spur_node_arc: " << graph.Tail(after_spur_node_arc)
396 << " - " << graph.Head(after_spur_node_arc) << " (" << source
397 << " - " << destination << ")";
398 arc_lengths_for_detour[after_spur_node_arc] =
400 }
401 // Ensure that the path computed from the new weights is loopless by
402 // "removing" the nodes of the root path from the graph (by tweaking the
403 // weights, again). The previous operation only disallows the arc from the
404 // spur node (at the end of the root path) to the next node in the
405 // previously found paths.
406 for (int node_position = 0; node_position < spur_node_position;
407 ++node_position) {
408 for (const int arc : graph.OutgoingArcs(root_path[node_position])) {
409 arc_lengths_for_detour[arc] = internal::kDisconnectedDistance;
410 }
411 }
412 VLOG(3) << " arc_lengths_for_detour: "
413 << absl::StrJoin(arc_lengths_for_detour, " - ");
414
415 // Generate a new candidate path from the spur node to the destination
416 // without using the forbidden arcs.
417 {
418 std::tuple<std::vector<NodeIndex>, PathDistance> detour_path =
419 internal::ComputeShortestPath(graph, arc_lengths_for_detour,
420 spur_node, destination);
421
422 if (std::get<0>(detour_path).empty()) {
423 // Node unreachable after some arcs are forbidden.
424 continue;
425 }
426 VLOG(2) << " detour_path: "
427 << absl::StrJoin(std::get<0>(detour_path), " - ") << " ("
428 << std::get<0>(detour_path).size()
429 << "): " << std::get<1>(detour_path);
430 std::vector<NodeIndex> spur_path = std::move(std::get<0>(detour_path));
431 if (ABSL_PREDICT_FALSE(spur_path.empty())) continue;
432
433#ifndef NDEBUG
434 CHECK_EQ(root_path.back(), spur_path.front());
435 CHECK_EQ(spur_node, spur_path.front());
436
437 if (spur_path.size() == 1) {
438 CHECK_EQ(spur_path.front(), destination);
439 } else {
440 // Ensure there is an edge between the end of the root path
441 // and the beginning of the spur path (knowing that both subpaths
442 // coincide at the spur node).
443 const bool root_path_leads_to_spur_path = absl::c_any_of(
444 graph.OutgoingArcs(root_path.back()),
445 [&graph, node_after_spur_in_spur_path = *(spur_path.begin() + 1)](
446 const typename GraphType::ArcIndex arc_index) {
447 return graph.Head(arc_index) == node_after_spur_in_spur_path;
448 });
449 CHECK(root_path_leads_to_spur_path);
450 }
451
452 // Ensure the forbidden arc is not present in any previously generated
453 // path.
454 for (absl::Span<const NodeIndex> previous_path : paths.paths) {
455 if (previous_path.size() <= spur_node_position + 1) continue;
456 const bool has_same_prefix_as_root_path = std::equal(
457 root_path.begin(), root_path.end(), previous_path.begin(),
458 previous_path.begin() + root_path.length());
459 if (has_same_prefix_as_root_path) {
460 CHECK_NE(spur_path[1], previous_path[spur_node_position + 1])
461 << "Forbidden arc " << previous_path[spur_node_position]
462 << " - " << previous_path[spur_node_position + 1]
463 << " is present in the spur path "
464 << absl::StrJoin(spur_path, " - ");
465 }
466 }
467#endif // !defined(NDEBUG)
468
469 // Assemble the new path.
470 std::vector<NodeIndex> new_path;
471 absl::c_copy(root_path.subspan(0, spur_node_position),
472 std::back_inserter(new_path));
473 absl::c_copy(spur_path, std::back_inserter(new_path));
474
475 DCHECK_EQ(new_path.front(), source);
476 DCHECK_EQ(new_path.back(), destination);
477
478#ifndef NDEBUG
479 // Ensure the assembled path is loopless, i.e. no node is repeated.
480 {
481 absl::flat_hash_set<NodeIndex> visited_nodes(new_path.begin(),
482 new_path.end());
483 CHECK_EQ(visited_nodes.size(), new_path.size());
484 }
485#endif // !defined(NDEBUG)
486
487 // Ensure the new path is not one of the previously known ones. This
488 // operation is required, as there are two sources of paths from the
489 // source to the destination:
490 // - `paths`, the list of paths that is output by the function: there
491 // is no possible duplicate due to `arc_lengths_for_detour`, where
492 // edges that might generate a duplicate path are forbidden.
493 // - `variant_path_queue`, the list of potential paths, ordered by
494 // their cost, with no impact on `arc_lengths_for_detour`.
495 // TODO(user): would it be faster to fingerprint the paths and
496 // filter by fingerprints? Due to the probability of error with
497 // fingerprints, still use this slow-but-exact code, but after
498 // filtering.
499 const bool is_new_path_already_known = std::any_of(
500 variant_path_queue.container().cbegin(),
501 variant_path_queue.container().cend(),
502 [&new_path](const internal::PathWithPriority<GraphType>& element) {
503 return element.path() == new_path;
504 });
505 if (is_new_path_already_known) continue;
506
507 const PathDistance path_length =
508 internal::ComputePathLength(graph, arc_lengths, new_path);
509 VLOG(5) << " New potential path generated: "
510 << absl::StrJoin(new_path, " - ") << " (" << new_path.size()
511 << ")" << " with length " << path_length;
512 VLOG(5) << " Root: " << absl::StrJoin(root_path, " - ") << " ("
513 << root_path.size() << ")";
514 VLOG(5) << " Spur: " << absl::StrJoin(spur_path, " - ") << " ("
515 << spur_path.size() << ")";
516 variant_path_queue.emplace(
517 /*priority=*/path_length, /*path=*/std::move(new_path));
518 }
519 }
520
521 // Add the shortest spur path ever found that has not yet been added. This
522 // can be a spur path that has just been generated or a previous one, if
523 // this iteration found no shorter one.
524 if (variant_path_queue.empty()) break;
525
526 const internal::PathWithPriority<GraphType>& next_shortest_path =
527 variant_path_queue.top();
528 VLOG(5) << "> New path generated: "
529 << absl::StrJoin(next_shortest_path.path(), " - ") << " ("
530 << next_shortest_path.path().size() << ")";
531 paths.paths.emplace_back(next_shortest_path.path());
532 paths.distances.push_back(next_shortest_path.priority());
533 variant_path_queue.pop();
534 }
535
536 return paths;
537}
538
539} // namespace operations_research
540
541#endif // OR_TOOLS_GRAPH_K_SHORTEST_PATHS_H_
std::vector< NodeIndex > NodePathTo(NodeIndex node) const
const std::vector< NodeIndex > & RunBoundedDijkstra(NodeIndex source_node, DistanceType distance_limit)
const ByNode< DistanceType > & distances() const
The distance of the nodes from their source.
const std::vector< NodeIndex > & path() const
bool operator>(const PathWithPriority &other) const
PathWithPriority(PathDistance priority, std::vector< NodeIndex > path)
const PathDistance kDisconnectedDistance
std::tuple< std::vector< typename GraphType::NodeIndex >, PathDistance > ComputeShortestPath(const GraphType &graph, const std::vector< PathDistance > &arc_lengths, const typename GraphType::NodeIndex source, const typename GraphType::NodeIndex destination)
GraphType::ArcIndex FindArcIndex(const GraphType &graph, const typename GraphType::NodeIndex source, const typename GraphType::NodeIndex destination)
PathDistance ComputePathLength(const GraphType &graph, const absl::Span< const PathDistance > arc_lengths, const absl::Span< const typename GraphType::NodeIndex > path)
Computes the total length of a path.
In SWIG mode, we don't want anything besides these top-level includes.
KShortestPaths< GraphType > YenKShortestPaths(const GraphType &graph, const std::vector< PathDistance > &arc_lengths, typename GraphType::NodeIndex source, typename GraphType::NodeIndex destination, unsigned k)
BlossomGraph::NodeIndex NodeIndex
STL namespace.
std::vector< std::vector< typename GraphType::NodeIndex > > paths
std::vector< PathDistance > distances