Introduction
C++ can be defined as a general-purpose programming language that is widely used nowadays for competitive programming. It’s imperative, object-oriented, and generic programming features. C++ runs on many platforms like Windows, Linux, Unix, Mac, etc. C++ has numerous in-built functions which help us in Competitive programming also as development. While using CPP as our language, we do not get to know everything. We do not get to implement data structures whenever we are using CPP unless it’s asked within the problem because we’ve STL in CPP. STL is an acronym for a normal template library. It’s a group of C++ template classes that provide generic classes and performance, which will be wont to implement data structures and algorithms. STL provides numerous containers and algorithms which are very useful in competitive programming. These are required in almost every question, for instance, you’ll very easily define a linked list with a single statement by using a list container of container library in STL or a stack or queue, etc. It saves a lot of time during the contest.
Check out this C++ course.
STL (Standard template library) is a kind of generic library that contains the same container or algorithm that is often operated on any data type; you don’t need to define an equivalent algorithm for various sorts of elements; we can just use them from STL.
For example, a sort algorithm will sort the weather within the given range regardless of their data type. We don’t need to implement different sort algorithms for various data types.
STL containers help us implement algorithms that need more than one data structure, and now we will learn how it can help and save time.
Today in this article, we’ll study what’s the graph and what’s Dijkstra’s algorithm in c++. Further, we’ll study the instance of Dijkstra’s algorithm in c++ code alongside its corresponding output. We’ll also further study the sensible application of this algorithm within the world. So, let’s get started!
What is Graph?
The graph may be a non-linear arrangement that involves nodes and edges. The nodes are the vertices, and the edges connect the 2 nodes within the graph. Therefore, the graph is often defined as a group of vertices and a group of edges that connect the nodes. If we consider Facebook as a graph, then the gathering of individuals on Facebook is taken into account as nodes. Therefore the connection between them is often considered as edges.
Vertex: Each node of the graph is named a vertex. Within the above graph, A, B, C, and D are the vertices of the graph.
Edge: The link or path between two vertices is named a foothold. It connects two or more vertices. The various edges within the above graph are AB, BC, AD, and DC.
Adjacent node: during a graph, if two nodes are connected by a foothold, then they’re called adjacent nodes or neighbors. Within the above graph, edge AB connects the vertices A and B.so, A and B are adjacent nodes.
Degree of the node: the number of edges that are connected to a specific node is named the degree of the node. Within the above graph, node A features a degree 2.
Path: The sequence of nodes that we’d like to follow once we need to travel from one vertex to a different during a graph is named the trail. In our example graph, if we’d like to travel from node A to C, then the trail would be A->B->C.
Closed path: If the initial node is the same as a terminal node, then that path is termed because of the closed path.
Simple path: A closed path is named an easy path during which all the opposite nodes are distinct.
Cycle: A path during which there are no repeated edges or vertices, and therefore the first and last vertices are equivalent to a cycle. within the above graph, A->B->C->D->A may be a cycle.
Connected Graph: A connected graph is the one during which there’s a path between each vertex. this suggests that there’s not one vertex that is isolated or without a connecting edge. The graph shown above may be a connected graph.
Complete Graph: A graph is named the entire graph during which each node is connected to a different node. If N is the total number of nodes during a graph, then the entire graph contains N(N-1)/2 number of edges.
Weighted graph: A positive value assigned to every edge indicating its length (distance between the vertices connected by an edge) is named weight. The graph containing weighted edges is named a weighted graph. The load of a foothold e is denoted by w(e), indicating the value of traversing a foothold.
Diagraph: A digraph may be a graph during which every edge is related to a selected direction, and therefore the traversal is often wiped out specified direction only.
What is Dijkstra’s Algorithm?
Dijkstra’s algorithm is additionally referred to as the shortest path algorithm. It’s an algorithm that wants to find the shortest path between nodes of the graph. The algorithm creates the tree of the shortest paths from the starting source vertex from all other points within the graph. It differs from the minimum spanning tree because the shortest distance between two vertices might not be included altogether in the vertices of the graph. The algorithm works by building or creating a group of nodes with a minimum distance from the beginning point. Here, Dijkstra’s algorithm in c++ uses a greedy approach to unravel the matter and find the simplest solution.
Let’s just understand how this algorithm works and gives us the shortest path between the source and the destination.
Dijkstra’s algorithm in c++ allows us to seek out the shortest path between any two vertices of a graph.
It differs from the minimum spanning tree because the shortest distance between two vertices won’t include all the vertices of the graph.
How Dijkstra’s Algorithm works
Dijkstra’s Algorithm follows the idea that any subpath from B to D of the shortest path from A to D between vertices A and D is additionally the shortest path between vertices B and D.
Dijkstra’s algorithm employs the shortest subpath property.
Each subpath is that the shortest path. Djikstra used this property in the other way, i.e., we overestimate the space of every vertex from the starting vertex. Then we visit each node and its neighbors to seek out the shortest subpath to those neighbors.
The algorithm uses a greedy approach to discover the subsequent best solution, hoping that the top result’s the simplest solution for the entire problem.
Rules we follow while working on Dijkstra’s algorithm:-
First of all, we’ll mark all vertex as unvisited vertex
Then, we’ll mark the source vertex as 0 and every other vertex as infinity
Consider source vertex as current vertex
Calculate the trail length of all the neighboring vertex from the present vertex by adding the load of the string within the current vertex
Now, we will check if the new path length is smaller than the previous path length, then we will replace it; otherwise, ignore it
Mark the present vertex as visited after visiting the neighbor vertex of the current vertex
Select the vertex with the littlest path length because of the new current vertex and return to step 4.
We will repeat this process unless all the vertices are marked as visited.
Once we undergo the algorithm, we will backtrack to the source vertex and find our shortest path.
Pseudo Code of Dijkstra Algorithm using set data structures from STL.
const int INF = 1e7;//defining the value of inf as 10000000
vector<vector<pair<int, int>>> adj;//adjacency list
void dijkstra(int s, vector<int> & d, vector<int> & p) {//function for implementing Dijkstra algo
int n = adj.size();// assigning the value of n which is equal to the size of adjency list
d.assign(n, INF);
p.assign(n, -1);
d[s] = 0;
set<pair<int, int>> q;
q.insert({0, s});
while (!q.empty()) {
int v = q.begin()->second;
q.erase(q.begin());//erasing the starting point
for (auto edge : adj[v]) {//range based loop
int to = edge.first;//assigning to= first edge
int len = edge.second;//assigning len = second edge
if (d[v] + len < d[to]) {//checking if d[v]+len id lesser than d[to]
q.erase({d[to], to});//if the condition satisfies then we will erase the q
d[to] = d[v] + len;//assigning d[to]= d[v]+len
p[to] = v;// assigning p[to]=v;
q.insert({d[to], to});//Inserting the element
}
}
}
}
Now let’s just one problem on Dijsktras Algo.
#include <bits/stdc++.h>
using namespace std;
template<typename T>//Template with which we can add any data type
class Graph {//class graph
map<T, list<pair<T, int>>> l;//declaration of nested map l with T and list of pairs
public://public object
void addEdge(T x, T y, int wt) {//function addEdge will add anew edge in the graph
l[x].push_back({y, wt});
l[y].push_back({x, wt});//to make the graph unidirectional just remove this line
//These line will make the graph directional
}
void print() {
for (auto p : l) {
T node = p.first;
cout << node << " -> ";
for (auto nbr : l[node]) {
cout << "(" << nbr.first << "," << nbr.second << ") ";
} cout << endl;
}
}
void djikstraSSSP(T src) {
map<T, int> dist;
// Initialising dist to inf
for (auto p : l) {
T node = p.first;
dist[node] = INT_MAX;
}
dist[src] = 0;
// set created to get the min dist element at the beginning
// dist, node
set<pair<int, T>> s;
s.insert({dist[src], src});
while (!s.empty()) {
pair<int, T> p = *s.begin();//defining pair T of int and T
s.erase(s.begin());
T currNode = p.second;
int currNodeDist = p.first;
// visit all nbrs of node
for (auto nbr : l[currNode]) {//range based loop
T nbrNode = nbr.first;
int distInBetween = nbr.second;
int nbrNodeDist = dist[nbrNode];
// Potential new distance = currNodeDist + distInBetween
if (currNodeDist + distInBetween < nbrNodeDist) {
// Update dist in both set and map
// If node not present in set then add it
auto pr = s.find({dist[nbrNode], nbrNode});
if (pr != s.end()) {
s.erase(pr);
}
dist[nbrNode] = currNodeDist + distInBetween;
s.insert({dist[nbrNode], nbrNode});
}
}
}
for (auto x : dist) {
cout << x.first << " is at distance " << x.second << " from source" << endl;
}
}
};
int main() {
Graph<string> g;
g.addEdge("Amritsar", "Delhi", 1);//Adding some edges in the graph
g.addEdge("Amritsar", "Jaipur", 4);
g.addEdge("Delhi", "Jaipur", 2);
g.addEdge("Mumbai", "Jaipur", 8);
g.addEdge("Bhopal", "Agra", 2);
g.addEdge("Mumbai", "Bhopal", 3);
g.addEdge("Agra", "Delhi", 1);
g.print();
cout << endl;
g.djikstraSSSP("Amritsar");
cout << endl;
g.djikstraSSSP("Delhi");
}
Output Snippets
Agra -> (Bhopal,2) (Delhi,1)
Amritsar -> (Delhi,1) (Jaipur,4)
Bhopal -> (Agra,2) (Mumbai,3)
Delhi -> (Amritsar,1) (Jaipur,2) (Agra,1)
Jaipur -> (Amritsar,4) (Delhi,2) (Mumbai,8)
Mumbai -> (Jaipur,8) (Bhopal,3)
Agra is at distance 2 from source
Amritsar is at distance 0 from source
Bhopal is at distance 4 from source
Delhi is at distance 1 from source
Jaipur is at distance 3 from source
Mumbai is at distance 7 from source
Agra is at distance 1 from source
Amritsar is at distance 1 from source
Bhopal is at distance 3 from source
Delhi is at distance 0 from source
Jaipur is at distance 2 from source
Mumbai is at distance 6 from source
ADVANTAGES OF DIJKSTRA’S ALGORITHM
• Once it’s been administered, you’ll find the smallest amount of weight path to all or any permanently labeled nodes.
• You don’t need a replacement diagram for every pass.
• Dijkstra’s algorithm has a time complexity of O(n^2), so it’s efficient enough to use for relatively large problems.
DISADVANTAGES OF DIJKSTRA’S ALGORITHM
• The main disadvantage of the Dijkstra’s algorithm in C++ is the indisputable fact that it does a blind search, thereby consuming tons of your time, wasting necessary resources.
• Another disadvantage is that it is not applicable for a graph with negative edges. This results in acyclic graphs and most frequently cannot obtain the proper shortest path.
APPLICATIONS
• Traffic information systems such as Google Maps uses Dijkstra’s algorithm to trace the shortest distance between the source and destinations from a given particular starting point.
Which uses a link-state within the individual areas that structure’s the hierarchy. The computation is predicated on Dijkstra’s algorithm, which calculates the shortest path in the tree inside each area of the network.
• OSPF- Open Shortest Path First, mostly used in Internet routing.
These were a few of the applications, but there is a lot more for this algorithm.
RELATED ALGORITHMS
A* algorithm is a graph/tree search algorithm mostly used in Artificial Intelligence that finds a path from a given initial node to a given goal node. It employs a ” heuristic estimate” h(x) that provides an estimate of the simplest route that goes through that node. It visits the nodes, so as of this heuristic estimate. It follows the approach of the breadth-first search.
