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);
41 void FindPath(
int dest, std::vector<int>* nodes)
const;
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_;
51 void BellmanFord::Initialize() {
52 for (
int i = 0; i < node_count_; i++) {
56 distance_[start_node_] = 0;
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;
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) {
90 void BellmanFord::FindPath(
int dest, std::vector<int>* nodes)
const {
93 while (predecessor_[j] != -1) {
94 nodes->push_back(predecessor_[j]);
108 FindPath(end_node, nodes);
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);
static constexpr int64 kInfinity
bool ShortestPath(int end_node, std::vector< int > *nodes)
BellmanFord(int node_count, int start_node, std::function< int64(int, int)> graph, int64 disconnected_distance)
static const int64 kint64max
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)