RetroSearch Browse

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

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/da/de8/dijkstra__greedy_8cpp_source.html below:

TheAlgorithms/C++: greedy_algorithms/dijkstra_greedy.cpp Source File

Go to the documentation of this file. 38

std::vector<std::vector<int>> edges{};

46

this->edges = std::vector<std::vector<int>>(V, std::vector<int>(V, 0));

47 for

(

int

i = 0; i < V; i++) {

48

edges[i] = std::vector<int>(V, 0);

52 for

(

int

i = 0; i < V; i++) {

53 for

(

int

j = 0; j < V; j++) {

68 void add_edge

(

int

src,

int

dst,

int

weight) {

69

this->edges[src][dst] = weight;

83 int

minVal = INT_MAX, minInd = 0;

84 for

(

int

i = 0; i < V; i++) {

85 if

(!vset[i] && (mdist[i] < minVal)) {

104void print

(std::vector<int> dist,

int

V) {

105

std::cout <<

"\nVertex Distance\n"

;

106 for

(

int

i = 0; i < V; i++) {

107 if

(dist[i] < INT_MAX) {

108

std::cout << i <<

"\t"

<< dist[i] <<

"\n"

;

111

std::cout << i <<

"\tINF"

"\n"

;

125 int

V =

graph

.vertexNum;

126

std::vector<int> mdist{};

127

std::vector<bool> vset{};

130 for

(

int

i = 0; i < V; i++) {

138 for

(

int

count = 0; count < V - 1; count++) {

143 for

(

int

v = 0; v < V; v++) {

144 if

(!vset[v] &&

graph

.edges[u][v] &&

145

mdist[u] +

graph

.edges[u][v] < mdist[v]) {

146

mdist[v] = mdist[u] +

graph

.edges[u][v];

164 graph

.add_edge(6, 2, 4);

165 graph

.add_edge(2, 6, 4);

167

assert(

graph

.edges[6][2] == 4);

170 graph

.add_edge(0, 1, 1);

171 graph

.add_edge(1, 0, 1);

173

assert(

graph

.edges[0][1] == 1);

176 graph

.add_edge(0, 2, 7);

177 graph

.add_edge(2, 0, 7);

178 graph

.add_edge(1, 2, 1);

179 graph

.add_edge(2, 1, 1);

181

assert(

graph

.edges[0][2] == 7);

184 graph

.add_edge(1, 3, 3);

185 graph

.add_edge(3, 1, 3);

186 graph

.add_edge(1, 4, 2);

187 graph

.add_edge(4, 1, 2);

188 graph

.add_edge(2, 3, 2);

190

assert(

graph

.edges[1][3] == 3);

192

std::cout <<

"All tests have successfully passed!\n"

;

Wrapper class for storing a graph.

void add_edge(int src, int dst, int weight)

Adds an edge to the graph.

Graph(const int V)

Constructs a graph.

static void tests()

Self-test implementations.

int main()

Main function.

void print(std::vector< int > dist, int V)

Utility function to print the distances to vertices.

int minimum_distance(std::vector< int > mdist, std::vector< bool > vset, int V)

Utility function that finds the vertex with the minimum distance in mdist.

void dijkstra(Graph graph, int src)

The main function that finds the shortest path from a given source to all other vertices using Dijkst...

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