Answers for "shortest path algorithm in a DAG"

C++
0

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;
}
Posted by: Guest on August-18-2021

Code answers related to "shortest path algorithm in a DAG"

Browse Popular Code Answers by Language