Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
greedy_algorithms::dijkstra Namespace Reference

Functions for the Dijkstra algorithm implementation. More...

Classes

class  Graph
 Wrapper class for storing a graph. More...
 

Functions

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 print (std::vector< int > dist, int V)
 Utility function to print the distances to vertices.
 
void dijkstra (Graph graph, int src)
 The main function that finds the shortest path from a given source to all other vertices using Dijkstra's Algorithm.
 

Detailed Description

Functions for the Dijkstra algorithm implementation.

Function Documentation

◆ dijkstra()

void greedy_algorithms::dijkstra::dijkstra ( Graph graph,
int src )

The main function that finds the shortest path from a given source to all other vertices using Dijkstra's Algorithm.

Note
This doesn't work on negative weights.
Parameters
graphthe graph to be processed
srcthe source of the given vertex
Returns
void
124 {
125 int V = graph.vertexNum;
126 std::vector<int> mdist{}; // Stores updated distances to the vertex
127 std::vector<bool> vset{}; // `vset[i]` is true if the vertex `i` is included in the shortest path tree
128
129 // Initialize `mdist and `vset`. Set the distance of the source as zero
130 for (int i = 0; i < V; i++) {
131 mdist[i] = INT_MAX;
132 vset[i] = false;
133 }
134
135 mdist[src] = 0;
136
137 // iterate to find the shortest path
138 for (int count = 0; count < V - 1; count++) {
139 int u = minimum_distance(mdist, vset, V);
140
141 vset[u] = true;
142
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];
147 }
148 }
149 }
150
151 print(mdist, V);
152}
Graph Algorithms.
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.
Definition dijkstra.cpp:82
Here is the call graph for this function:

◆ minimum_distance()

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

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

Parameters
mdistarray of distances to each vertex
vsetarray indicating inclusion in the shortest path tree
Vthe number of vertices in the graph
Returns
index of the vertex with the minimum distance
82 {
83 int minVal = INT_MAX, minInd = 0;
84 for (int i = 0; i < V; i++) {
85 if (!vset[i] && (mdist[i] < minVal)) {
86 minVal = mdist[i];
87 minInd = i;
88 }
89 }
90
91 return minInd;
92}

◆ print()

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

Utility function to print the distances to vertices.

This function prints the distances to each vertex in a tabular format. If the distance is equal to INT_MAX, it is displayed as "INF".

Parameters
distAn array representing the distances to each vertex.
VThe number of vertices in the graph.
Returns
void
104 {
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";
109 }
110 else {
111 std::cout << i << "\tINF" << "\n";
112 }
113 }
114}