OR-Tools  8.2
bellman_ford.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 <utility>
17 #include <vector>
18 
21 
22 namespace operations_research {
23 class BellmanFord {
24  public:
25  static constexpr int64 kInfinity = kint64max / 2;
26 
27  BellmanFord(int node_count, int start_node,
28  std::function<int64(int, int)> graph, int64 disconnected_distance)
29  : node_count_(node_count),
30  start_node_(start_node),
31  graph_(std::move(graph)),
32  disconnected_distance_(disconnected_distance),
33  distance_(new int64[node_count_]),
34  predecessor_(new int[node_count_]) {}
35  bool ShortestPath(int end_node, std::vector<int>* nodes);
36 
37  private:
38  void Initialize();
39  void Update();
40  bool Check() const;
41  void FindPath(int dest, std::vector<int>* nodes) const;
42 
43  const int node_count_;
44  const int start_node_;
45  std::function<int64(int, int)> graph_;
46  const int64 disconnected_distance_;
47  std::unique_ptr<int64[]> distance_;
48  std::unique_ptr<int[]> predecessor_;
49 };
50 
51 void BellmanFord::Initialize() {
52  for (int i = 0; i < node_count_; i++) {
53  distance_[i] = kint64max / 2;
54  predecessor_[i] = -1;
55  }
56  distance_[start_node_] = 0;
57 }
58 
59 void BellmanFord::Update() {
60  for (int i = 0; i < node_count_ - 1; i++) {
61  for (int u = 0; u < node_count_; u++) {
62  for (int v = 0; v < node_count_; v++) {
63  const int64 graph_u_v = graph_(u, v);
64  if (graph_u_v != disconnected_distance_) {
65  const int64 other_distance = distance_[u] + graph_u_v;
66  if (distance_[v] > other_distance) {
67  distance_[v] = other_distance;
68  predecessor_[v] = u;
69  }
70  }
71  }
72  }
73  }
74 }
75 
76 bool BellmanFord::Check() const {
77  for (int u = 0; u < node_count_; u++) {
78  for (int v = 0; v < node_count_; v++) {
79  const int graph_u_v = graph_(u, v);
80  if (graph_u_v != disconnected_distance_) {
81  if (distance_[v] > distance_[u] + graph_u_v) {
82  return false;
83  }
84  }
85  }
86  }
87  return true;
88 }
89 
90 void BellmanFord::FindPath(int dest, std::vector<int>* nodes) const {
91  int j = dest;
92  nodes->push_back(j);
93  while (predecessor_[j] != -1) {
94  nodes->push_back(predecessor_[j]);
95  j = predecessor_[j];
96  }
97 }
98 
99 bool BellmanFord::ShortestPath(int end_node, std::vector<int>* nodes) {
100  Initialize();
101  Update();
102  if (distance_[end_node] == kInfinity) {
103  return false;
104  }
105  if (!Check()) {
106  return false;
107  }
108  FindPath(end_node, nodes);
109  return true;
110 }
111 
112 bool BellmanFordShortestPath(int node_count, int start_node, int end_node,
113  std::function<int64(int, int)> graph,
114  int64 disconnected_distance,
115  std::vector<int>* nodes) {
116  BellmanFord bf(node_count, start_node, std::move(graph),
117  disconnected_distance);
118  return bf.ShortestPath(end_node, nodes);
119 }
120 } // namespace operations_research
static constexpr int64 kInfinity
Definition: bellman_ford.cc:25
bool ShortestPath(int end_node, std::vector< int > *nodes)
Definition: bellman_ford.cc:99
BellmanFord(int node_count, int start_node, std::function< int64(int, int)> graph, int64 disconnected_distance)
Definition: bellman_ford.cc:27
static const int64 kint64max
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool BellmanFordShortestPath(int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)