19 #include "absl/container/flat_hash_set.h"
30 bool operator<(
const Element& other)
const {
31 return distance_ != other.distance_ ? distance_ > other.distance_
32 : node_ > other.node_;
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_; }
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) {}
67 int node = SelectClosestNode(&distance);
71 }
else if (node == end_node) {
78 FindPath(end_node, nodes);
85 for (
int i = 0; i < node_count_; i++) {
86 elements_[i].set_node(i);
87 if (i == start_node_) {
89 elements_[i].set_distance(0);
90 frontier_.
Add(&elements_[i]);
93 predecessor_[i] = start_node_;
94 not_visited_.insert(i);
99 int SelectClosestNode(
int64* distance) {
100 const int node = frontier_.
Top()->node();
101 *distance = frontier_.
Top()->distance();
103 not_visited_.erase(node);
104 added_to_the_frontier_.erase(node);
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);
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);
121 predecessor_[other_node] = node;
127 void FindPath(
int dest, std::vector<int>* nodes) {
130 while (predecessor_[j] != -1) {
131 nodes->push_back(predecessor_[j]);
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_;
144 S added_to_the_frontier_;
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);
157 std::function<
int64(
int,
int)> graph,
158 int64 disconnected_distance,
159 std::vector<int>* nodes) {
161 disconnected_distance);