RetroSearch Browse

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

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d8/d68/dijkstra_8cpp_source.html below:

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

Go to the documentation of this file. 34constexpr

int64_t

INF

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

48void addEdge

(std::vector<std::vector<std::pair<int, int>>> *adj,

int

50

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

66int dijkstra

(std::vector<std::vector<std::pair<int, int>>> *adj,

int

t) {

71

std::vector<int64_t> dist(n,

INF

);

76

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,

77

std::greater<std::pair<int, int>>>

81

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

88 int

currentNode = pq.top().second;

91 int

currentDist = pq.top().first;

97 for

(std::pair<int, int> edge : (*adj)[currentNode]) {

99 if

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

100

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

101

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

105 if

(dist[t] !=

INF

) {

114

std::cout <<

"Initiatinig Predefined Tests..."

<< std::endl;

115

std::cout <<

"Initiating Test 1..."

<< std::endl;

116

std::vector<std::vector<std::pair<int, int>>> adj1(

117

4, std::vector<std::pair<int, int>>());

125

std::cout <<

"Test 1 Passed..."

<< std::endl;

128

std::cout <<

"Initiating Test 2..."

<< std::endl;

130

std::cout <<

"Test 2 Passed..."

<< std::endl;

132

std::vector<std::vector<std::pair<int, int>>> adj2(

133

5, std::vector<std::pair<int, int>>());

145

std::cout <<

"Initiating Test 3..."

<< std::endl;

147

std::cout <<

"Test 3 Passed..."

<< std::endl;

148

std::cout <<

"All Test Passed..."

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

156 int

vertices = int(), edges = int();

157

std::cout <<

"Enter the number of vertices : "

;

158

std::cin >> vertices;

159

std::cout <<

"Enter the number of edges : "

;

162

std::vector<std::vector<std::pair<int, int>>> adj(

163

vertices, std::vector<std::pair<int, int>>());

165 int

u = int(), v = int(), w = int();

167

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

171 int

s = int(), t = int();

175

std::cout <<

"Target not reachable from source"

<< std::endl;

177

std::cout <<

"Shortest Path Distance : "

<< dist << std::endl;

constexpr int64_t INF

for assert

void addEdge(std::vector< std::vector< int > > *adj, int u, int v)

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

int dijkstra(std::vector< std::vector< std::pair< int, int > > > *adj, int s, int t)

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

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