Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist
Edsger W. Dijkstra in 1956 and published three years later.
Here we have demonstrated the algo by finding the shortest path from a source to a prticular destination.
#include<bits/stdc++.h>
using namespace std;
class Solution
{
public:
//Function to find the shortest distance of all the vertices
//from the source vertex S.
vector dijkstra(int V, vector> adj[], int S)
{
// Code here
priority_queue, vector >, greater>> pq;
vector dista(V, INT_MAX); //1-indexed array for calculating shortest paths
dista[S] = 0;
pq.push(make_pair(0, S)); // (dist,source)
while ( !pq.empty() ) {
int dist = pq.top().first;
int node = pq.top().second;
pq.pop();
//vector >::iterator it;
for (auto it : adj[node]) {
int edge_weight = it[1];
int adj_node = it[0];
if ( dista[adj_node] > edge_weight + dist) {
dista[adj_node] = edge_weight + dist;
pq.push(make_pair(dista[adj_node], adj_node));
}
}
}
return dista;
}
};
int main()
{
int t;
cin >> t;
while (t--) {
int V, E;
cin >> V >> E;
vector> adj[V];
int i = 0;
while (i++ < E) {
int u, v, w;
cin >> u >> v >> w;
vector t1, t2;
t1.push_back(v);
t1.push_back(w);
adj[u].push_back(t1);
t2.push_back(u);
t2.push_back(w);
adj[v].push_back(t2);
}
int S;
cin >> S;
Solution obj;
vector res = obj.dijkstra(V, adj, S);
for (int i = 0; i < V; i++)
cout << res[i] << " ";
cout << endl;
}
return 0;
}