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++
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
Vertex Distance from source
- 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.
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.