In this article, we will study what is the graph and what is Dijkstra's algorithm. Further, we will study the example of Dijkstra's algorithm and its c++ code along with its corresponding output. We will also further study the practical application of this algorithm in the real world. So let's get started!

## What is Graph?

The graph is a non-linear data structure that involves nodes and edges. The nodes are the vertices and edges are the lines that connect the two nodes in the graph. Therefore, the graph can be defined as a set of vertices and a set of edges that connect the nodes. If we consider Facebook as a graph then the collection of people on Facebook is considered as nodes and the connection between them can be considered as edges.

## What is Dijkstra’s Algorithm?

Dijkstra’s algorithm is also known as the shortest path algorithm. It is an algorithm used 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 in the graph. It differs from the minimum spanning tree as the shortest distance between two vertices may not be included in all the vertices of the graph. The algorithm works by building a set of nodes that have a minimum distance from the source. Here, Dijkstra's algorithm uses a greedy approach to solve the problem and find the best solution.

## Algorithm for Dijkstra’s in C++

- First of all, we will mark all vertex as unvisited vertex
- Then, we will mark the source vertex as 0 and all other vertex as infinity
- Consider source vertex as current vertex
- Calculate the path length of all the neighboring vertex from the current vertex by adding the weight of the edge in the current vertex
- Now, if the new path length is smaller than the previous path length then replace it otherwise ignore it
- Mark the current vertex as visited after visiting the neighbour vertex of current vertex
- Select the vertex with the smallest path length as the new current vertex and go back to step 4.
- Repeat this process until all the vertex are marked as visited.

Once we go through the algorithm, we can backtrack the source vertex and find our shortest path.

## Pseudocode of Dijkstra’s Algorithm in C++

function dijkstra(G, S) for each vertex V in G dist[V] <- infinite prev[V] <- NULL If V != S, add V to Priority Queue Q dist[S] <- 0 while Q IS NOT EMPTY U <- Extract MIN from Q for each unvisited neighbour V of U temperoryDist <- dist[U] + edgeWeight(U, V) if temperoryDist < dist[V] dist[V] <- temperoryDist prev[V] <- U return dist[], prev[]

**Example**

Let us consider the below example to understand the algorithm. Choosing the starting vertex as assign 0 to it. And assign infinity path values to all other devices.

**Go to each vertex and update its path length**

**If the new path length is smaller than the previous path length then update it with a smaller value. As shown below we update vertex B from infinity to 10 and vertex C from infinity to 3.**

**Now select the vertex with the smaller path length as visited vertex and put it in the answer.**

**Visit its neighbouring nodes of visited vertex and update the path lengths as required. Do not update the path length of the already visited vertex.**

**Therefore, after each loop, we consider the unvisited vertex with the smaller path length.**

**Repeat the process until all vertices have been visited**

## C++ code for Dijkstra’s Algorithm

#include #include using namespace std; int miniDist(int distance[], bool Tset[]) // finding minimum distance { int minimum=INT_MAX,ind; for(int k=0;k<6;k++) { if(Tset[k]==false && distance[k]<=minimum) { minimum=distance[k]; ind=k; } } return ind; } void DijkstraAlgo(int graph[6][6],int src) // adjacency matrix { int distance[6]; // // array to calculate the minimum distance for each node bool Tset[6];// boolean array to mark visited and unvisited for each node for(int k = 0; k<6; k++) { distance[k] = INT_MAX; Tset[k] = false; } distance[src] = 0; // Source vertex distance is set 0 for(int k = 0; k<6; k++) { int m=miniDist(distance,Tset); Tset[m]=true; for(int k = 0; k<6; k++) { // updating the distance of neighbouring vertex if(!Tset[k] && graph[m][k] && distance[m]!=INT_MAX && distance[m]+graph[m][k]<distance[k]) distance[k]=distance[m]+graph[m][k]; } } cout<<"Vertex\t\tDistance from source vertex"<<endl; for(int k = 0; k<6; k++) { char str=65+k; cout<<str<<"\t\t\t"<<distance[k]<<endl; } } int main() { int graph[6][6]={ {0, 1, 2, 0, 0, 0}, {1, 0, 0, 5, 1, 0}, {2, 0, 0, 2, 3, 0}, {0, 5, 2, 0, 2, 2}, {0, 1, 3, 2, 0, 1}, {0, 0, 0, 2, 1, 0}}; DijkstraAlgo(graph,0); return 0; }

**Output**

Vertex Distance from source

A 0

B 1

C 2

D 4

E 2

F 3

## Application

- Dijkstra’s algorithm is used as a routing protocol required by the routers to update their forwarding table.
- It is used to find the shortest distance between two locations along the path on google maps.
- It is used in telephone networking to find the shortest path for finding the nearest switching station for transmission.
- Dijkstra’s algorithm is used to find the shortest path between users measured through handshakes or connection among them.
- Dijkstra’s algorithm is used to minimize the number of hops in computer networks.

## Conclusion

As Dijkstra's algorithm has its own importance in the real world, it is most recommended to learn and understand Dijkstra's algorithm. Therefore, in the above article, we studied what is Dijkstra's algorithm and its algorithm steps to get the result. We also studied the pseudo code and c++ code for finding the shortest path between two points aLong with the practical application of the algorithm.