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
22namespace operations_research {
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
51void 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
59void 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
76bool 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
90void 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
99bool 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
112bool 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)
STL namespace.