RetroSearch Browse

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_source.html below:

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

24constexpr

int64_t

INF

= std::numeric_limits<int64_t>::max();

46void addEdge

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

47

std::vector<std::vector<std::pair<uint64_t, uint64_t>>> *adj2,

48

uint64_t u, uint64_t v, uint64_t w) {

49

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

50

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

63 const

std::vector<uint64_t> &workset_,

64 const

std::vector<std::vector<uint64_t>> &distance_) {

65

int64_t distance =

INF

;

66 for

(uint64_t i : workset_) {

67 if

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

68

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

87int Bidijkstra

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

88

std::vector<std::vector<std::pair<uint64_t, uint64_t>>> *adj2,

89

uint64_t s, uint64_t t) {

91

uint64_t n = adj1->size();

94

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

INF

));

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>>>>

108

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

110

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

113

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

119

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

129 if

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

133

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

136

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

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));

150

workset.push_back(currentNode);

153 if

(visited[currentNode] == 1) {

156

visited[currentNode] =

true

;

161 if

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

165

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

168

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

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));

182

workset.push_back(currentNode);

185 if

(visited[currentNode] == 1) {

188

visited[currentNode] =

true

;

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>>());

212

uint64_t s = 1, t = 3;

215

std::cout <<

"Test 1 Passed..."

<< std::endl;

218

std::cout <<

"Initiating Test 2..."

<< std::endl;

221

std::cout <<

"Test 2 Passed..."

<< std::endl;

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>>());

238

std::cout <<

"Initiating Test 3..."

<< std::endl;

241

std::cout <<

"Test 3 Passed..."

<< std::endl;

242

std::cout <<

"All Test Passed..."

<< std::endl << std::endl;

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 : "

;

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>>());

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 " 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" 270

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

273

std::cout <<

"Enter the next edge"

<< std::endl;

277

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

279

"Enter the source node and the target node separated by a space" 281

std::cout <<

"Example: If the source node is 5 and the target node is 6 " 282 "enter: 5 6 and press enter" 288

std::cout <<

"Target not reachable from source"

<< std::endl;

290

std::cout <<

"Shortest Path Distance : "

<< dist << std::endl;

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...

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

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.

int main()

Main function.

Functions for [Bidirectional Dijkstra Shortest Path] (https://www.coursera.org/learn/algorithms-on-gr...

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