Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
dijkstra.cpp File Reference

Graph Dijkstras Shortest Path Algorithm (Dijkstra's Shortest Path) More...

#include <cassert>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <utility>
#include <vector>
Include dependency graph for dijkstra.cpp:

Namespaces

 graph
 Graph algorithms.
 

Functions

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. More...
 
int graph::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 returns the shortest distance of target from the source. More...
 
void tests ()
 
int main ()
 

Variables

constexpr int64_t INF = std::numeric_limits<int64_t>::max()
 

Detailed Description

Graph Dijkstras Shortest Path Algorithm (Dijkstra's Shortest Path)

Author
Ayaan Khan

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.

Function Documentation

◆ main()

int main ( void  )

Main function

152  {
153  // running predefined tests
154  tests();
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 
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;
168  graph::addEdge(&adj, u, v, w);
169  }
170 
171  int s = int(), t = int();
172  std::cin >> s >> t;
173  int dist = graph::dijkstra(&adj, s - 1, t - 1);
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 }
Here is the call graph for this function:

◆ tests()

void tests ( )

Function to test the Algorithm

113  {
114  std::cout << "Initiatinig Predefined Tests..." << std::endl;
115  std::cout << "Initiating Test 1..." << std::endl;
118  graph::addEdge(&adj1, 1, 2, 1);
119  graph::addEdge(&adj1, 4, 1, 2);
120  graph::addEdge(&adj1, 2, 3, 2);
121  graph::addEdge(&adj1, 1, 3, 5);
122 
123  int s = 1, t = 3;
124  assert(graph::dijkstra(&adj1, s - 1, t - 1) == 3);
125  std::cout << "Test 1 Passed..." << std::endl;
126 
127  s = 4, t = 3;
128  std::cout << "Initiating Test 2..." << std::endl;
129  assert(graph::dijkstra(&adj1, s - 1, t - 1) == 5);
130  std::cout << "Test 2 Passed..." << std::endl;
131 
134  graph::addEdge(&adj2, 1, 2, 4);
135  graph::addEdge(&adj2, 1, 3, 2);
136  graph::addEdge(&adj2, 2, 3, 2);
137  graph::addEdge(&adj2, 3, 2, 1);
138  graph::addEdge(&adj2, 2, 4, 2);
139  graph::addEdge(&adj2, 3, 5, 4);
140  graph::addEdge(&adj2, 5, 4, 1);
141  graph::addEdge(&adj2, 2, 5, 3);
142  graph::addEdge(&adj2, 3, 4, 4);
143 
144  s = 1, t = 5;
145  std::cout << "Initiating Test 3..." << std::endl;
146  assert(graph::dijkstra(&adj2, s - 1, t - 1) == 6);
147  std::cout << "Test 3 Passed..." << std::endl;
148  std::cout << "All Test Passed..." << std::endl << std::endl;
149 }
Here is the call graph for this function:
std::pair
std::vector
STL class.
tests
void tests()
Definition: dijkstra.cpp:113
graph::dijkstra
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...
Definition: dijkstra.cpp:66
std::cout
graph::addEdge
void addEdge(std::vector< std::vector< int >> *adj, int u, int v)
Function that add edge between two nodes or vertices of graph.
Definition: connected_components.cpp:46
std::endl
T endl(T... args)
std::cin