[Graph Dijkstras Shortest Path Algorithm (Dijkstra's Shortest Path)] (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) More...
#include <cassert>#include <iostream>#include <limits>#include <memory>#include <queue>#include <utility>#include <vector>
Go to the source code of this file.
void graph::addEdge (std::vector< std::vector< std::pair< int, int > > > *adj, int u, int v, int w) Function that add edge between two nodes or vertices of graph.[Graph Dijkstras Shortest Path Algorithm (Dijkstra's Shortest Path)] (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
Dijkstra's Algorithm is used to find the shortest path from a source vertex to all other reachable vertex in the graph. The algorithm initially assumes all the nodes are unreachable from the given source vertex so we mark the distances of all vertices as INF (infinity) from source vertex (INF / infinity denotes unable to reach).
in similar fashion with BFS we assume the distance of source vertex as 0 and pushes the vertex in a priority queue with it's distance. we maintain the priority queue as a min heap so that we can get the minimum element at the top of heap
Basically what we do in this algorithm is that we try to minimize the distances of all the reachable vertices from the current vertex, look at the code below to understand in better way.
Definition in file dijkstra.cpp.
◆ main()Main function
Definition at line 152 of file dijkstra.cpp.
152 {
153
155
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 : ";
160 std::cin >> edges;
161
162 std::vector<std::vector<std::pair<int, int>>> adj(
163 vertices, std::vector<std::pair<int, int>>());
164
165 int u = int(), v = int(), w = int();
166 while (edges--) {
167 std::cin >> u >> v >> w;
169 }
170
171 int s = int(), t = int();
172 std::cin >> s >> t;
174 if (dist == -1) {
175 std::cout << "Target not reachable from source" << std::endl;
176 } else {
177 std::cout << "Shortest Path Distance : " << dist << std::endl;
178 }
179 return 0;
180}
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...
◆ tests()Function to test the Algorithm
Definition at line 113 of file dijkstra.cpp.
113 {
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>>());
122
123 int s = 1, t = 3;
125 std::cout << "Test 1 Passed..." << std::endl;
126
127 s = 4, t = 3;
128 std::cout << "Initiating Test 2..." << std::endl;
130 std::cout << "Test 2 Passed..." << std::endl;
131
132 std::vector<std::vector<std::pair<int, int>>> adj2(
133 5, std::vector<std::pair<int, int>>());
143
144 s = 1, t = 5;
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;
149}
◆ INF int64_t INF = std::numeric_limits<int64_t>::max() constexprDefinition at line 34 of file dijkstra.cpp.
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