The shortest distance between two nodes in a graph is an important concept in computer science and mathematics. The problem of finding the shortest distance between two nodes can be solved using various algorithms such as Dijkstra's algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm. In this article, we will discuss the shortest distance between two nodes in a graph using Dijkstra's algorithm in C++.
Dijkstra's algorithm is a popular algorithm for finding the shortest path between two nodes in a graph. It is a greedy algorithm that utilizes a priority queue to determine the shortest path between two nodes. The algorithm starts at the source node and explores all the neighboring nodes, updating the distance of each node from the source node. The algorithm continues this process until it reaches the destination node.
The algorithm can be implemented in C++ using an adjacency list representation of a graph. An adjacency list is a data structure that stores the edges of a graph in a list. Each node in the graph is represented by a list of its neighboring nodes. The following is an example of an adjacency list representation of a graph:
int main()
{ int V = 9; vector<pair<int, int>> adj[V]; // adding edges to the graph
addEdge(adj, 0, 1, 4); addEdge(adj, 0, 7, 8); addEdge(adj, 1, 2, 8); addEdge(adj, 1, 7, 11); addEdge(adj, 2, 3, 7); addEdge(adj, 2, 8, 2); addEdge(adj, 2, 5, 4); addEdge(adj, 3, 4, 9); addEdge(adj, 3, 5, 14); addEdge(adj, 4, 5, 10); addEdge(adj, 5, 6, 2); addEdge(adj, 6, 7, 1); addEdge(adj, 6, 8, 6); addEdge(adj, 7, 8, 7); dijkstra(adj, 0, V); return 0; }
The above code creates a graph with 9 nodes and 13 edges. The addEdge() function is used to add edges to the graph. The first parameter of the function is the adjacency list, the second parameter is the source node, and the third parameter is the destination node. The fourth parameter is the weight of the edge.
To implement Dijkstra's algorithm, we need to create a priority queue that stores the nodes and their distances from the source node. The priority queue is implemented using the STL library in C++. The following is an example of a priority queue:
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
The priority queue stores pairs of integers representing the node and its distance from the source node. The greater<> class is used to sort the pairs based on the distance. The STL vector class is used to store the pairs in the priority queue.
The dijkstra() function is used to find the shortest path between two nodes. The function takes three parameters: the adjacency list, the source node, and the number of nodes in the graph. The following is an example of the dijkstra() function:
void dijkstra(vector<pair<int, int>> adj[], int src, int V)
{
// array to store the shortest distance from the source node
int dist[V];// initialize the distance array with infinity for(int i = 0; i < V; i++) dist[i] = INT_MAX; // create a priority queue priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // insert the source node into the priority queue pq.push(make_pair(0, src)); dist[src] = 0; // loop until the priority queue is empty while(!pq.empty())
{ // get the node with the smallest distance from the source node int u = pq.top().second; pq.pop(); // loop through the neighboring nodes of the current node for(auto i : adj[u])
{ int v = i.first;
int weight = i.second; // if the distance of the neighboring node is greater than the current node + weight of the edge
// update the distance and insert the neighboring node into the priority queue
if(dist[v] > dist[u] + weight)
{ dist[v] = dist[u] + weight; pq.push(make_pair(dist[v], v)); }
}
}
// print the shortest distance from the source node to all other nodes for(int i = 0; i < V; i++) cout << i << " " << dist[i] << endl;
}
In this example, the dijkstra() function starts by initializing an array that stores the shortest distance from the source node. The distance array is initialized with the maximum value of an integer, indicating that the distance is infinite. The source node is inserted into the priority queue with a distance of 0.
The function then loops until the priority queue is empty. In each iteration, the node with the smallest distance from the source node is removed from the priority queue. The function then loops through the neighboring nodes of the current node and updates the distance if the new distance is shorter than the previous distance. The neighboring node is then inserted into the priority queue with the updated distance.
Finally, the function prints the shortest distance from the source node to all other nodes. The output of the program would be as follows:
0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
In conclusion, Dijkstra's algorithm is a powerful and efficient algorithm for finding the shortest distance between two nodes in a graph. The algorithm can be implemented in C++ using an adjacency list representation of a graph and a priority queue. The implementation of Dijkstra's algorithm in C++ is an essential tool for solving many problems in computer science and mathematics. It is also a great way to understand and practice the use of data structures like priority queue, which are useful in various applications like scheduling, navigation and many more.
