OR-Tools  8.1
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 
24 namespace operations_research {
25 namespace {
26 
27 // Priority queue element
28 class 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 
48 template <class S>
49 class DijkstraSP {
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 
147 bool 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 
156 bool 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
integral_types.h
adjustable_priority_queue.h
AdjustablePriorityQueue::Top
T * Top()
Definition: adjustable_priority_queue.h:87
AdjustablePriorityQueue::NoteChangedPriority
void NoteChangedPriority(T *val)
Definition: adjustable_priority_queue.h:74
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
AdjustablePriorityQueue::Add
void Add(T *val)
Definition: adjustable_priority_queue.h:49
int64
int64_t int64
Definition: integral_types.h:34
shortestpaths.h
operations_research::DijkstraSP::DijkstraSP
DijkstraSP(int node_count, int start_node, std::function< int64(int, int)> graph, int64 disconnected_distance)
Definition: dijkstra.cc:53
operations_research::DijkstraShortestPath
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
operations_research::StableDijkstraShortestPath
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
operations_research::DijkstraSP::ShortestPath
bool ShortestPath(int end_node, std::vector< int > *nodes)
Definition: dijkstra.cc:62
AdjustablePriorityQueue::IsEmpty
bool IsEmpty() const
Definition: adjustable_priority_queue.h:127
operations_research::DijkstraSP::kInfinity
static constexpr int64 kInfinity
Definition: dijkstra.cc:51
AdjustablePriorityQueue< Element >
kint64max
static const int64 kint64max
Definition: integral_types.h:62
AdjustablePriorityQueue::Pop
void Pop()
Definition: adjustable_priority_queue.h:117
operations_research::DijkstraSP
Definition: dijkstra.cc:49