//Author: Bishal Sarang //Dijkstra Priority Queue Implementation /* Sampe Input 5 6 0 1 1 0 2 4 1 2 2 2 4 4 1 3 4 3 4 4 0 4 */ #include #define MAX 100 #define INF 1000000 using namespace std; //Adjacency List //Array of Vector Pair vector< pair> adj[MAX]; //Store Distance of Vertex long long dist[MAX]; //Store parent of Vertex int path[MAX]; //Method to print shortest path void print_path(int d, int s) { //d = destination and s = source if(d == s) { cout << d << " -> "; return; } print_path(path[d], s); cout << d << " -> "; } //dijkstra Procedure void dijkstra(int s, int v) { //Initialize all distances to infinite memset(dist, INF, sizeof(dist)); //Initialize all parent vertex to -1 memset(path, -1, sizeof(path)); //Declare priority que to extract minimum distance every time priority_queue< pair , vector>, greater>> pq; //Initialize priority que with infinite distance and all the vertices for(int i = 0; i < v; i++) { pq.push({INF, i}); } //Set distance from source to source as 0 dist[s] = 0; pq.push({0, s}); while(!pq.empty()) { //Extract minimum weight and pop it int w = pq.top().first; int u = pq.top().second; pq.pop(); //For neighbours of vertex extracted for(auto v: adj[u]) { //Relax //dist[v.second] --> distance of vertex v which is neighbour of u //if dist[v.second] is greater than sum of dist[parent] + edge //set dist[v.second] to minm of them if( dist[v.second] > dist[u] + v.first ) { dist[v.second] = dist[u] + v.first; //Push new distance of vertex v pq.push({dist[v.second], v.second}); //Set parent of vertex v to u path[v.second] = u; } } } } int main() { //freopen("dijkstra.txt", "r", stdin); int vertex, edges; cin >> vertex >> edges; int u, v, w; for(int i = 0; i < edges; i++) { cin >> u >> v >> w; adj[u].push_back({w, v}); adj[v].push_back({w, u}); } int s; cin >> s; dijkstra(s, vertex); int destination; cin >> destination; cout << "Shortest Path from " << s << " to " << destination << " is : \n" ; print_path(destination, s); cout << "and distnace is " << dist[destination]; cout << "\n Shortest Distance : \n"; for(int i = 0; i < vertex ; i++) { //If no Path Exist if(dist[i] >= INF) cout << -1 << " "; else if(i != s) cout << "SP " << s << " to " << i << " is: " << dist[i] << "\n"; } return 0; }

Dijkstra(Algorithms C++)