DAG 1

#include<bits/stdc++.h>
using namespace std ;

vector<int>Graph[1000];
bool visited[1000];
int topologicalSort[1000];
bool top[1000];
int cost[1000][1000];
int path[1000];
int dis[1000];
int n;
void inputGraph()
{
    int vertex,edge;


    printf("Enter the number of vertex : ");
    scanf("%d",&vertex);
    n=vertex;
    printf("\nEnter the number of edges : ");
    scanf("%d",&edge);
    for(int i = 1 ; i<=edge ; i++)
    {
        printf("\nInput edge no %d : ",i);
        int u,v;
        scanf("%d %d",&u,&v);
        printf("Cost: ");
        scanf("%d",&cost[u][v]);
        Graph[u].push_back(v);
    }
}

void TopologicalSort()
{
    printf("Topological Sort: \n");
    stack<int>s;
    stack<int>tp;
    int i,j;

    for(j=1; j<=n; j++)
    {
        s.push(j);
        visited[j]=true ;
        while(!s.empty())
        {
            for(i = 0 ; i<Graph[s.top()].size() ; i++)
            {
                if(visited[Graph[s.top()][i]]==false)
                {
                    visited[Graph[s.top()][i]]=true ;
                    s.push(Graph[s.top()][i]);
                    i = -1 ;
                }
            }
            if(top[s.top()]==false)
            {
                tp.push(s.top());
                top[s.top()]=true;
            }

            s.pop();
        }
    }
    i=0;
    while(!tp.empty())
    {
        printf("%d -> ",tp.top());
        topologicalSort[i]=tp.top();
        i++;
        tp.pop();
    }
    printf("End!\n");
}

int selectSource()
{
    int sr;
    printf("\nEnter the source node for DAG shortest path: ");
    scanf("%d",&sr);
    return sr;
}

void InitilizeSingleSource(int source)
{
    for(int j=1; j<=n; j++)
    {
        path[j]=0;
        dis[j]=99999;
    }
    dis[source]=0;

}
void relax(int u,int v)
{
    if(dis[v]>dis[u]+cost[u][v])
    {
        dis[v]=dis[u]+cost[u][v];
        path[v]=u;
    }
}
void DAG(int source)
{
    InitilizeSingleSource(source);
    int i,j;
    for(i=0; i<n; i++)
    {
        for(j = 0 ; j<Graph[topologicalSort[i]].size() ; j++)
        {
            relax(topologicalSort[i],Graph[topologicalSort[i]][j]);
        }
    }


    //Print
    for(i=1; i<=n; i++)
    {
        printf("\nFor Node %d: ",i);
        if(dis[i]<99999)
            printf("\nCost from source : %d\n\nPath: ",dis[i]);
        else
            printf("\nCost from source : Infinity\n\nPath: ",dis[i]);

        stack <int> s;
        s.push(i);
        while(s.top()!=0)
        {
            s.push(path[s.top()]);
        }
        while(!s.empty())
        {
            if(s.top()!=0)
                printf("%d -> ",s.top());
            s.pop();
        }
        printf("End!\n");
    }

}
int main()
{
    int source;
    inputGraph();

    TopologicalSort();
    DAG(selectSource());
    return 0 ;
}