Dijkstra’s Shortest Path Algorithm

#include<bits/stdc++.h>

#define pii pair<int, int>

#define inf 1<<30

using namespace std;

void dijstkra(vector<int>adj[], vector<int>cost[], int node, int source)

{

int distance[node+5];

for(int i=0;i<=node;i++)

distance[i] = inf;

priority_queue<pii, vector<pii>, greater<pii>> pq;

pq.push(pii(0, source));

distance[source] = 0;

while(!pq.empty())

{

int start = pq.top().second;

pq.pop();

for(int i=0; i<adj[start].size();i++)

{

int finish = adj[start][i];

if(distance[start] + cost[start][i] < distance[finish])

{

distance[finish] = distance[start] + cost[start][i];

pq.push(pii(distance[finish], finish));

}

}

}

for(int i=1;i<=node;i++)

cout << source << " node to " << i << " node distance :: " << distance[i] << "\n";

}

int main()

{

int node, edge, source, u, v, w;

cout << "Enter Node Number :: ";

cin >> node;

cout << "Enter Edge Number :: ";

cin >> edge;

vector<int>adj[node+5], cost[node+5];

cout << "Enter node and weight :: \n";

for(int i=1;i<=edge;i++)

{

cin >> u >> v >> w;

adj[u].push_back(v);

adj[v].push_back(u);

cost[u].push_back(w);

cost[v].push_back(w);

}

cout << "Enter Source :: ";

cin >> source;

dijstkra(adj, cost, node, source);

return 0;

}