shortest path algorithm in a DAG
//Shortest path in DAG
#include<bits/stdc++.h>
using namespace std;
void addedge(vector<pair<int,int>>adj[],int u,int v,int weight)
{
adj[u].push_back(make_pair(v,weight));
}
void topo(int node,vector<pair<int,int>>adj[],int visited[],stack<int>&st)
{
visited[node]=1;
for(auto it:adj[node])
{
if(!visited[it.first])
{
topo(it.first,adj,visited,st);
}
}
st.push(node);
}
void shortestpath(vector<pair<int,int>>adj[],int source,int n)
{
int vist[n]={0};
stack<int>st;
for(int i=0;i<n;i++)
{
if(!vist[i])
{
topo(i,adj,vist,st);
}
}
int dist[n];
for(int i=0;i<n;i++)
{
dist[i]=INT_MAX;
}
dist[source]=0;
while(!st.empty())
{
int node=st.top();
st.pop();
if(dist[node!=INT_MAX])
{
for(auto it: adj[node])
{
if(dist[node]+it.second<dist[it.first])
{
dist[it.first]=dist[node]+it.second;
}
}
}
}
for(int i=0;i<n;i++)
{
if(dist[i]==INT_MAX)
{
cout<<"imf"<<" ";
}
else
{
cout<<dist[i]<<" ";
}
}
}
int main()
{
int vertex,edges;
cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
cin>>vertex>>edges;
vector<pair<int,int>>adj[vertex];
int a,b,w;
cout<<"ENTER THE LINKS:"<<endl;
for(int i=0;i<edges;i++)
{
cin>>a>>b>>w;
addedge(adj,a,b,w);
}
int src;
cout<<"ENTER THE NODE FROM WHICH SHORTEST PATH IS MEANT TO BE FOUND:"<<endl;
cin>>src;
shortestpath(adj,src,vertex);
return 0;
}