Functions for the Dijkstra algorithm implementation.
More...
|
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.
|
|
Functions for the Dijkstra algorithm implementation.
◆ 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
-
graph | the graph to be processed |
src | the source of the given vertex |
- Returns
- void
124 {
125 int V =
graph.vertexNum;
128
129
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
138 for (int count = 0; count < V - 1; count++) {
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}
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
◆ 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
-
mdist | array of distances to each vertex |
vset | array indicating inclusion in the shortest path tree |
V | the 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
-
dist | An array representing the distances to each vertex. |
V | The number of vertices in the graph. |
- Returns
- void
104 {
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 {
112 }
113 }
114}