OR-Tools  8.2
dijkstra.cc
Go to the documentation of this file.
1// Copyright 2010-2018 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#include <functional>
15#include <memory>
16#include <set>
17#include <vector>
18
19#include "absl/container/flat_hash_set.h"
23
24namespace operations_research {
25namespace {
26
27// Priority queue element
28class Element {
29 public:
30 bool operator<(const Element& other) const {
31 return distance_ != other.distance_ ? distance_ > other.distance_
32 : node_ > other.node_;
33 }
34 void SetHeapIndex(int h) { heap_index_ = h; }
35 int GetHeapIndex() const { return heap_index_; }
36 void set_distance(int64 distance) { distance_ = distance; }
37 int64 distance() const { return distance_; }
38 void set_node(int node) { node_ = node; }
39 int node() const { return node_; }
40
41 private:
42 int64 distance_ = 0;
43 int heap_index_ = -1;
44 int node_ = -1;
45};
46} // namespace
47
48template <class S>
50 public:
51 static constexpr int64 kInfinity = kint64max / 2;
52
53 DijkstraSP(int node_count, int start_node,
54 std::function<int64(int, int)> graph, int64 disconnected_distance)
55 : node_count_(node_count),
56 start_node_(start_node),
57 graph_(std::move(graph)),
58 disconnected_distance_(disconnected_distance),
59 predecessor_(new int[node_count]),
60 elements_(node_count) {}
61
62 bool ShortestPath(int end_node, std::vector<int>* nodes) {
63 Initialize();
64 bool found = false;
65 while (!frontier_.IsEmpty()) {
66 int64 distance;
67 int node = SelectClosestNode(&distance);
68 if (distance == kInfinity) {
69 found = false;
70 break;
71 } else if (node == end_node) {
72 found = true;
73 break;
74 }
75 Update(node);
76 }
77 if (found) {
78 FindPath(end_node, nodes);
79 }
80 return found;
81 }
82
83 private:
84 void Initialize() {
85 for (int i = 0; i < node_count_; i++) {
86 elements_[i].set_node(i);
87 if (i == start_node_) {
88 predecessor_[i] = -1;
89 elements_[i].set_distance(0);
90 frontier_.Add(&elements_[i]);
91 } else {
92 elements_[i].set_distance(kInfinity);
93 predecessor_[i] = start_node_;
94 not_visited_.insert(i);
95 }
96 }
97 }
98
99 int SelectClosestNode(int64* distance) {
100 const int node = frontier_.Top()->node();
101 *distance = frontier_.Top()->distance();
102 frontier_.Pop();
103 not_visited_.erase(node);
104 added_to_the_frontier_.erase(node);
105 return node;
106 }
107
108 void Update(int node) {
109 for (const auto& other_node : not_visited_) {
110 const int64 graph_node_i = graph_(node, other_node);
111 if (graph_node_i != disconnected_distance_) {
112 if (added_to_the_frontier_.find(other_node) ==
113 added_to_the_frontier_.end()) {
114 frontier_.Add(&elements_[other_node]);
115 added_to_the_frontier_.insert(other_node);
116 }
117 const int64 other_distance = elements_[node].distance() + graph_node_i;
118 if (elements_[other_node].distance() > other_distance) {
119 elements_[other_node].set_distance(other_distance);
120 frontier_.NoteChangedPriority(&elements_[other_node]);
121 predecessor_[other_node] = node;
122 }
123 }
124 }
125 }
126
127 void FindPath(int dest, std::vector<int>* nodes) {
128 int j = dest;
129 nodes->push_back(j);
130 while (predecessor_[j] != -1) {
131 nodes->push_back(predecessor_[j]);
132 j = predecessor_[j];
133 }
134 }
135
136 const int node_count_;
137 const int start_node_;
138 std::function<int64(int, int)> graph_;
139 const int64 disconnected_distance_;
140 std::unique_ptr<int[]> predecessor_;
142 std::vector<Element> elements_;
143 S not_visited_;
144 S added_to_the_frontier_;
145};
146
147bool DijkstraShortestPath(int node_count, int start_node, int end_node,
148 std::function<int64(int, int)> graph,
149 int64 disconnected_distance,
150 std::vector<int>* nodes) {
152 node_count, start_node, std::move(graph), disconnected_distance);
153 return bf.ShortestPath(end_node, nodes);
154}
155
156bool StableDijkstraShortestPath(int node_count, int start_node, int end_node,
157 std::function<int64(int, int)> graph,
158 int64 disconnected_distance,
159 std::vector<int>* nodes) {
160 DijkstraSP<std::set<int>> bf(node_count, start_node, std::move(graph),
161 disconnected_distance);
162 return bf.ShortestPath(end_node, nodes);
163}
164} // namespace operations_research
static constexpr int64 kInfinity
Definition: dijkstra.cc:51
DijkstraSP(int node_count, int start_node, std::function< int64(int, int)> graph, int64 disconnected_distance)
Definition: dijkstra.cc:53
bool ShortestPath(int end_node, std::vector< int > *nodes)
Definition: dijkstra.cc:62
static const int64 kint64max
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool StableDijkstraShortestPath(int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)
Definition: dijkstra.cc:156
bool DijkstraShortestPath(int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)
Definition: dijkstra.cc:147
STL namespace.