Dijkstra’s Algorithm C++

Dijkstra’s algorithm is also known as the shortest possible path algorithm. It is the procedure to find the shortest path between the nodes/ edges of the graph. The shortest graph of a tree is created by starting from the source vertex to all the other points in the graph.

Algorithm

• Before direct implementation of the Dijkstra graph in the C programming language, we need to understand the working of this graph algorithm.
• The first step is the creation of “sptSet,” which is abbreviated as the shortest path tree set; it stores the 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 at the nodes are declared as INFINITE, as we don’t know the weight of the paths till now.
• Pick a vertex “u” that is not present already in sptSet and is of minimum value. Then include it to sptSet. After that, update the distance values of all those nodes that are adjacent vertices of “u.” This all is done under the loop until sptSet can contain all the vertices.

Implementation of Dijkstra’s graph algorithm

Here is the implementation of the Dijkstra graph, where a program is written for the adjacency matrix representation of that graph. Start the program by adding two libraries very essential for the accomplishment of the program in C programming language that makes us able to use cin and cout features.

After describing the libraries, now we will 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 of [9] [9].

“V” is for the vertices. As the algorithm requires many steps to accomplish the provided task, each step or process is divided into separate functions to perform them so that the code is clear and there is no ambiguity regarding the logic. Moreover, the complexity is also removed.

The function is created here to search the vertex that has a minimum distance value; it contains the set of vertices that are not included in the tree having the shortest path. The function will contain the distance array and a bool type sptset, the shortest path tree set, and the array as a parameter of the function. Inside the function, the minimum value is initialized by declaring a variable of integer type that will store the returned value. Two variables, max, and the min_index are introduced.

Int min =INT_MAX, min_index;

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image1-32.png" data-lazy- height="287" src="data:image/svg xml,” width=”475″>

A for loop is used here; in which a starting vertex in all vertices is taken, the loop will continue until all the vertices are traversed. A condition is applied here by using an if statement that checks if the shortest path set is false means, it is empty right now, and the distance of the vertex is smaller than that of the minimum value of the vertex, which is declared earlier, then allot the current value of vertex as min, and the min_index will also contain the same value of the vertex.

Min = dist[v], min_index = v;

After the minimum value of the vertex is calculated, next is the process of creating a function that will display the distance array that was constructed earlier. A loop will iterate each index that will be accessed and displayed. First, the vertex number is displayed starting from the zero value, and the distance of the vertex from the source is also mentioned here with a sequence. This function is declared here, but it will be called later in the program when the whole path is calculated as the shortest distance.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image3-29.png" data-lazy- height="259" src="data:image/svg xml,” width=”487″>

The main part of the whole source code is declared now, where the implementation of the single-source shortest path is calculated. A graph will be represented by the adjacency matrix representation. This function will take a graph matrix and the source as parameter values that will act as input for distance calculation. First, inside the function, we will declare the output array that will contain the shortest path from the source to a specific point. Secondly, a Boolean variable array is declared, which will return true if the vertex is included in determining the shortest path at the start.

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

All the distances will be set as infinite, and the shortest tree path array is false. With the help of a loop, all this process will take place.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image2-30.png" data-lazy- height="293" src="data:image/svg xml,” width=”583″>

Inside the loop, the minimum distance vertex is picked from the vertices set that are not processed yet. In the first iteration, ‘u’ is always equal to the source vertex.

Int u = minDistance(dist, sptSet);

Those vertices that are chosen and traversed are picked and marked as processed by setting the Boolean variable is true.

When one vertex is added, all the vertices adjacent to that particular vertex are also checked; this needs an update. So we will update the value of “dist” of the adjacent vertices of those vertices that have been picket till now.

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

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

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

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

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image5-28.png" data-lazy- height="329" src="data:image/svg xml,” width=”538″>

Save the whole code. Compile the code by using a g compiler in the Ubuntu terminal. ‘-o’ is a symbol that saves the output of the file.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image4-28.png" data-lazy- height="217" src="data:image/svg xml,” width=”464″>

You can see that all the vertices in each separate line are displayed along with the distance of every vertex from the source.

This code helps calculate the shortest distance, but it does not support calculating the information about the path. This source code is good for the undirected graphs but can be possible to use for the directed graphs as well. By using this code, we can find the shortest distance from the point of source to all other vertices in the graph.

The time complexity of the Dijkstra graph

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

This can be reduced to 0 (E log V) by using the process of the binary heap. The Dijkstra graph is not for the graphs that have negative weights.

Conclusion

This article contains the process of finding the shortest distance between the source node to 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 designed for undirected graphs. We have explained the process step by step with the source code to make it vivid for the new users. We hope that this effort will be up to the mark for the readers.