Dijkstras C++ Algorithm

The Dijkstras algorithm is also known as the shortest path algorithm. This is a procedure for finding the shortest path between nodes/edges of a graph. The shortest tree graph is created by going from the original vertex to all other points in the graph.

Algorithm

• Before directly implementing the Dijkstras graph in the C++ programming language, we need to understand how this graph algorithm works.

• The first step is to create a "sptSet", which is shorthand for a shortest path tree set; it stores a record of those vertices that are included in the shortest path. At the initial stage, this set is declared as NULL.

• In the next step, first all these values in the nodes are declared as INFINITE, since we still do not know the weight of the paths.

• Select a vertex "u" that is not yet in sptSet and has the minimum value. Then include it in sptSet. After that, update the distance values of all those nodes that are neighboring "u" vertices. All this is done in a loop until the sptSet can contain all the vertices.

Dijkstras Graph Algorithm Implementation

Here is an implementation of Dijkstra's graph, where a program is written to represent the adjacency matrix of this graph. Run the program by adding two libraries that are very necessary to run the program in the C++ programming language, which allow us to use the cin and cout functions.

#include <iostream>

#include <limits.h>

After describing the libraries, we will now provide the size or vertices of the graph in which we need the shortest path. We have given 9 vertices, which means that the matrix is a square [9] [9].

#define V 9

"V" for vertices. Since the algorithm requires many steps to complete the task at hand, each step or process is divided into separate functions to execute them so that the code is clear and there is no ambiguity about the logic. In addition, the difficulty has also been removed.

Here is a function to find the vertex with the minimum distance value; it contains the set of vertices not included in the tree that has the shortest path. The function will contain an array of distances and a boolean sptset, a shortest path tree set, and an array as a function parameter. Inside the function, the minimum value is initialized by declaring a variable of integer type that will store the return value. Two variables are introduced, max and min_index.

Int min =INT_MAX, min_index

The for loop is used here; which takes the starting vertex in all vertices, the loop will continue until all vertices have been traversed. The condition is applied here with an if statement that checks if the set of shortest paths is false, means it's empty right now and the vertex distance is less than the min vertex value declared before, then assign the current vertex value as min and min_index as well will contain the same vertex value.

Min = distance[v], min_index = v

After the minimum value of the vertex is calculated, the process of creating a function that will display the array of distances built earlier follows. The loop will iterate over each index that will be accessed and displayed. The vertex number is displayed first, starting at zero, and here, with a sequence, the distance of the vertex from the origin is mentioned. This function is declared here, but it will be called later in the program when the entire path has been calculated as the shortest distance.

Now the bulk of the entire source code is declared, where the implementation of the shortest path from a single source is calculated. The graph will be represented by an adjacency matrix representation. This function accepts a plot matrix and a source as parameter values that will act as input to the distance calculation. First, inside the function, we will declare an output array that will contain the shortest path from the source to a certain point. Second, an array of booleans is declared that will return true if the vertex is included in the definition of the shortest path at the beginning.

Int dist[v] ; bool sptset[v];

All distances will be set to infinite and the tree's shortest path array will be false. With the help of a loop, this whole process will take place.

Inside the loop, the minimum distance vertex is selected from the set of vertices that have not yet been processed. In the first iteration, 'u' is always equal to the original vertex.

Int u = minDistance(distance, sptSet);

Those vertices that are selected and traversed are selected and marked as processed by setting the boolean variable to true.

sptSet[u] = true;

When one vertex is added, all vertices adjacent to that particular vertex are also checked; it needs an update. This way we will update the "dist" value of the adjacent vertices of those vertices that have been picketed so far.

Inside this for loop, we will update dist[v] if and only if it is not in sptset, there is a line called an edge from vertex u to v, and the total weight of the path that starts from "src" to "v" passing through "u", less than the current value present in dist[v].

Dist[v] = dist[u] + graph[u][v];

After that, the print function we declared above is called by passing the dist[] array as a parameter.

printSolution(dist);

In the main program, we create a 9*9 matrix graph. And then the Dijkstra function is called, through which the graph is passed.

Save all code. Compile the code using the g++ compiler in the Ubuntu terminal. '-o' is the character that saves the output of the file.

$  g++  -o  dij dij.c

$. / against

You can see that all vertices are displayed on each individual line, along with each vertex's distance from the origin.

This code helps to calculate the shortest distance, but does not support the calculation of path information. This source code is good for undirected graphs, but can also be used for directed graphs. Using this code, we can find the shortest distance from the source point to all other vertices in the graph.

Time complexity of Dijkstras graph

We will talk about the time complexity of the implementation. It:

 (V^2).

This can be reduced to 0 (E log V) using the binary heap process. The Dijkstras graph is not intended for graphs with negative weights.

Conclusion

This article describes the process of finding the shortest distance between the original node and the rest of the nodes. There can be many approaches to this. But the Dijkstra graph is one of the best mechanisms for this purpose. It is intended for undirected graphs. We have explained the process step by step with source code to make it clear for new users. We hope that this attempt will be appreciated by readers.