To understand the implementation of Dijkstra's Algorithm using C++
Objective
To understand the implementation of Dijkstra's Algorithm using C++
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
void addEdge(vector <pair<int, int>> adj[], int u, int v, int wt) {
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
void dijkstra(vector> adj[], int V, int src) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(V, INF);
pq.push(make_pair(0, src));
dist[src] = 0;
while(!pq.empty()) {
int u = pq.top().second;
pq.pop();
for(auto x : adj[u]) {
int v = x.first;
int weight = x.second;
if(dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
cout << "Vertex | Distance from Source" << endl;
for(int i = 0; i < V; ++i) {
cout << i << "\t | \t\t" << dist[i] << endl;
}
}
int main() {
int V = 5;
vector<pair<int, int>> adj[V];
addEdge(adj, 0, 1, 10);
addEdge(adj, 0, 4, 5);
addEdge(adj, 1, 2, 1);
addEdge(adj, 1, 4, 2);
addEdge(adj, 2, 3, 4);
addEdge(adj, 3, 0, 7);
addEdge(adj, 3, 2, 6);
addEdge(adj, 4, 1, 3);
addEdge(adj, 4, 2, 9);
addEdge(adj, 4, 3, 2);
dijkstra(adj, V, 0);
return 0;
}
Discussion of Algorithm
- Start
- Set the source vertex distance as 0, and all other vertices as infinity
- Add the source vertex to a priority queue
-
While the priority queue is not empty:
- Extract the vertex with the smallest distance
- For each vertex v connected to u:
- If dist[u] + weight(u, v) < dist[v], update dist[v] to dist[u] + weight(u, v)
- Output the shortest distance from the source to all vertices
- End
Representations
Flow Diagram
+----------------------------------+ | | | Start | | | | +----------------------------------+ | V +----------------------------------+ | | | // Initialize variables | | and data structures | | int V = 5; | | vector<pair<int,int>> adj[V]; | | | | +----------------------------------+ | V +----------------------------------+ | | | // Add edges to the graph | | addEdge(adj, 0, 1, 10); | | ... | | addEdge(adj, 4, 3, 2); | | | | +----------------------------------+ | V +----------------------------------+ | | | Dijkstra's Algorithm | | (Shortest Path) | | | | priority_queue pq | | vector<int> dist(V, INF); | | dist[src] = 0; | | pq.push(make_pair(0, src)); | | | +----------------------------------+ | V +----------------------------------+ | | | Process nodes in the | | priority queue | | | | pq.pop(); | |if(dist[v] > dist[u] + weight) { | | dist[v] = dist[u] + weight; | | pq.push(make_pair(dist[v], v));| | } | +----------------------------------+ | V +----------------------------------+ | | | Print the distances | | from the source node | | | +----------------------------------+ | V +----------------------------------+ | | | Exit | | | | +----------------------------------+
Tabular Dry Run
Current Node | Visited Nodes | Distance from Source |
---|---|---|
0 | 0 | 0 |
1 | 0, 1 | 10 |
4 | 0, 1, 4 | 5 |
2 | 0, 1, 2, 4 | 7 |
3 | 0, 1, 2, 3, 4 | 9 |
Output
Vertex | Distance from Source 0 | 0 1 | 8 2 | 9 3 | 7 4 | 5