Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d7/d07/bidirectional__dijkstra_8cpp.html below:

TheAlgorithms/C++: graph/bidirectional_dijkstra.cpp File Reference

[Bidirectional Dijkstra Shortest Path Algorithm] (https://www.coursera.org/learn/algorithms-on-graphs/lecture/7ml18/bidirectional-dijkstra) More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

Go to the source code of this file.

[Bidirectional Dijkstra Shortest Path Algorithm] (https://www.coursera.org/learn/algorithms-on-graphs/lecture/7ml18/bidirectional-dijkstra)

This is basically the same Dijkstra Algorithm but faster because it goes from the source to the target and from target to the source and stops when finding a vertex visited already by the direct search or the reverse one. Here some simulations of it: https://www.youtube.com/watch?v=DINCL5cd_w0&t=24s

Definition in file bidirectional_dijkstra.cpp.

Function that add edge between two nodes or vertices of graph.

Parameters

adj1 adjacency list for the direct search adj2 adjacency list for the reverse search u any node or vertex of graph v any node or vertex of graph

Definition at line 46 of file bidirectional_dijkstra.cpp.

48 {

49 (*adj1)[u - 1].push_back(std::make_pair(v - 1, w));

50 (*adj2)[v - 1].push_back(std::make_pair(u - 1, w));

51

52}

Function runs the dijkstra algorithm for some source vertex and target vertex in the graph and returns the shortest distance of target from the source.

Parameters

adj1 input graph adj2 input graph reversed s source vertex t target vertex

Returns

shortest distance if target is reachable from source else -1 in case if target is not reachable from source.

n denotes the number of vertices in graph

setting all the distances initially to INF

creating a a vector of min heap using priority queue pq[0] contains the min heap for the direct search pq[1] contains the min heap for the reverse search

first element of pair contains the distance second element of pair contains the vertex

vector for store the nodes or vertices in the shortest path

vector for store the nodes or vertices visited

pushing the source vertex 's' with 0 distance in pq[0] min heap

marking the distance of source as 0

pushing the target vertex 't' with 0 distance in pq[1] min heap

marking the distance of target as 0

direct search

second element of pair denotes the node / vertex

first element of pair denotes the distance

for all the reachable vertex from the currently exploring vertex we will try to minimize the distance

minimizing distances

check if currentNode has already been visited

reversed search

second element of pair denotes the node / vertex

first element of pair denotes the distance

for all the reachable vertex from the currently exploring vertex we will try to minimize the distance

minimizing distances

check if currentNode has already been visited

Definition at line 87 of file bidirectional_dijkstra.cpp.

89 {

91 uint64_t n = adj1->size();

92

std::vector<std::vector<uint64_t>> dist(2, std::vector<uint64_t>(n,

));

95

99

102 std::vector<

103 std::priority_queue<std::pair<uint64_t, uint64_t>,

104 std::vector<std::pair<uint64_t, uint64_t>>,

105 std::greater<std::pair<uint64_t, uint64_t>>>>

106 pq(2);

108 std::vector<uint64_t> workset(n);

110 std::vector<bool> visited(n);

111

113 pq[0].push(std::make_pair(0, s));

114

116 dist[0][s] = 0;

117

119 pq[1].push(std::make_pair(0, t));

120

122 dist[1][t] = 0;

123

124 while (true) {

126

127

128

129 if (pq[0].size() == 0) {

130 break;

131 }

133 uint64_t currentNode = pq[0].top().second;

134

136 uint64_t currentDist = pq[0].top().first;

137

138 pq[0].pop();

139

142 for (std::pair<int, int> edge : (*adj1)[currentNode]) {

144 if (currentDist + edge.second < dist[0][edge.first]) {

145 dist[0][edge.first] = currentDist + edge.second;

146 pq[0].push(std::make_pair(dist[0][edge.first], edge.first));

147 }

148 }

149

150 workset.push_back(currentNode);

151

153 if (visited[currentNode] == 1) {

155 }

156 visited[currentNode] = true;

158

159

160

161 if (pq[1].size() == 0) {

162 break;

163 }

165 currentNode = pq[1].top().second;

166

168 currentDist = pq[1].top().first;

169

170 pq[1].pop();

171

174 for (std::pair<int, int> edge : (*adj2)[currentNode]) {

176 if (currentDist + edge.second < dist[1][edge.first]) {

177 dist[1][edge.first] = currentDist + edge.second;

178 pq[1].push(std::make_pair(dist[1][edge.first], edge.first));

179 }

180 }

181

182 workset.push_back(currentNode);

183

185 if (visited[currentNode] == 1) {

187 }

188 visited[currentNode] = true;

189 }

190 return -1;

191}

uint64_t Shortest_Path_Distance(const std::vector< uint64_t > &workset_, const std::vector< std::vector< uint64_t > > &distance_)

This function returns the shortest distance from the source to the target if there is path between ve...

constexpr int64_t INF

for assert

Main function.

Returns

0 on exit

Definition at line 249 of file bidirectional_dijkstra.cpp.

249 {

251 uint64_t vertices = uint64_t();

252 uint64_t edges = uint64_t();

253 std::cout << "Enter the number of vertices : ";

254 std::cin >> vertices;

255 std::cout << "Enter the number of edges : ";

256 std::cin >> edges;

257

258 std::vector<std::vector<std::pair<uint64_t, uint64_t>>> adj1(

259 vertices, std::vector<std::pair<uint64_t, uint64_t>>());

260 std::vector<std::vector<std::pair<uint64_t, uint64_t>>> adj2(

261 vertices, std::vector<std::pair<uint64_t, uint64_t>>());

262

263 uint64_t u = uint64_t(), v = uint64_t(), w = uint64_t();

264 std::cout << "Enter the edges by three integers in this form: u v w "

265 << std::endl;

266 std::cout << "Example: if there is and edge between node 1 and node 4 with "

267 "weight 7 enter: 1 4 7, and then press enter"

268 << std::endl;

269 while (edges--) {

270 std::cin >> u >> v >> w;

272 if (edges != 0) {

273 std::cout << "Enter the next edge" << std::endl;

274 }

275 }

276

277 uint64_t s = uint64_t(), t = uint64_t();

278 std::cout

279 << "Enter the source node and the target node separated by a space"

280 << std::endl;

281 std::cout << "Example: If the source node is 5 and the target node is 6 "

282 "enter: 5 6 and press enter"

283 << std::endl;

284 std::cin >> s >> t;

285 int dist =

287 if (dist == -1) {

288 std::cout << "Target not reachable from source" << std::endl;

289 } else {

290 std::cout << "Shortest Path Distance : " << dist << std::endl;

291 }

292

293 return 0;

294}

int Bidijkstra(std::vector< std::vector< std::pair< uint64_t, uint64_t > > > *adj1, std::vector< std::vector< std::pair< uint64_t, uint64_t > > > *adj2, uint64_t s, uint64_t t)

Function runs the dijkstra algorithm for some source vertex and target vertex in the graph and return...

static void tests()

Function to test the provided algorithm above.

void addEdge(std::vector< std::vector< std::pair< uint64_t, uint64_t > > > *adj1, std::vector< std::vector< std::pair< uint64_t, uint64_t > > > *adj2, uint64_t u, uint64_t v, uint64_t w)

Function that add edge between two nodes or vertices of graph.

This function returns the shortest distance from the source to the target if there is path between vertices 's' and 't'.

Parameters

workset_ vertices visited in the search distance_ vector of distances from the source to the target and from the target to the source

Definition at line 62 of file bidirectional_dijkstra.cpp.

64 {

int64_t distance =

;

66 for (uint64_t i : workset_) {

67 if (distance_[0][i] + distance_[1][i] < distance) {

68 distance = distance_[0][i] + distance_[1][i];

69 }

70 }

71 return distance;

72}

Function to test the provided algorithm above.

Returns

void

Definition at line 200 of file bidirectional_dijkstra.cpp.

200 {

201 std::cout << "Initiatinig Predefined Tests..." << std::endl;

202 std::cout << "Initiating Test 1..." << std::endl;

203 std::vector<std::vector<std::pair<uint64_t, uint64_t>>> adj1_1(

204 4, std::vector<std::pair<uint64_t, uint64_t>>());

205 std::vector<std::vector<std::pair<uint64_t, uint64_t>>> adj1_2(

206 4, std::vector<std::pair<uint64_t, uint64_t>>());

211

212 uint64_t s = 1, t = 3;

214 t - 1) == 3);

215 std::cout << "Test 1 Passed..." << std::endl;

216

217 s = 4, t = 3;

218 std::cout << "Initiating Test 2..." << std::endl;

220 t - 1) == 5);

221 std::cout << "Test 2 Passed..." << std::endl;

222

223 std::vector<std::vector<std::pair<uint64_t, uint64_t>>> adj2_1(

224 5, std::vector<std::pair<uint64_t, uint64_t>>());

225 std::vector<std::vector<std::pair<uint64_t, uint64_t>>> adj2_2(

226 5, std::vector<std::pair<uint64_t, uint64_t>>());

236

237 s = 1, t = 5;

238 std::cout << "Initiating Test 3..." << std::endl;

240 t - 1) == 6);

241 std::cout << "Test 3 Passed..." << std::endl;

242 std::cout << "All Test Passed..." << std::endl << std::endl;

243}

for assert

for io operations for variable INF for the priority_queue of distances for make_pair function for store the graph, the distances, and the path

Definition at line 24 of file bidirectional_dijkstra.cpp.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4