DAG (OWN)

#include<iostream>
#include<stack>
using namespace std;

int vertex,edge,source,time;
int adjacency_matrix[100][100],weight_matrix[100][100],cost[100];
int parent[100],Distance[100],Finishing_time[100],tSVertex[100],visited[100];
string color[100];
stack<int> result;
void inputGraph();
void doDFS();
void doDFSvisit(int);
void printTSpath();
void Initialize_Single_Source();
void relax();
void DAG();
void printCostAndPath();

int main(void)
{
    inputGraph();
    //initialize();
    doDFS();
    printTSpath();
    //printAll();
    Initialize_Single_Source();
    DAG();
    printCostAndPath();
    return 0;
}
void inputGraph()
{
    cout<<"Total vertex : ";
    cin>>vertex;
    cout<<"Total edge   : ";
    cin>>edge;
    int i,j;
    //make all weight infinity and vertex disconnected
    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            adjacency_matrix[i][j]=0;
            weight_matrix[i][j]=999999;
        }

    }
    // scan adjacency matrix and weight
    for(i=1; i<=edge; i++)
    {
        int start,finish;
        cout<<"Enter start and end node for edge "<<i<<" : ";
        cin>>start;
        cin>>finish;
        adjacency_matrix[start][finish]=1;
        cout<<"Enter weight for edge "<<i<<" : ";
        cin>>weight_matrix[start][finish];
    }
    cout<<"The adjacency matrix is : "<<endl;
    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            cout<<adjacency_matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"The weight matrix is : "<<endl;
    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            cout<<weight_matrix[i][j]<<" ";
        }
        cout<<endl;
    }
}

void doDFS()
{
    int i,j;
    for(i=1; i<=vertex; i++)
    {
        color[i]="white";
        parent[i]=0;
    }
    time=0;
    //super correction : add this line ( even in algorithm if need )
    doDFSvisit(source);
    //
    for(i=1; i<=vertex; i++)
    {
        if(color[i]=="white")
        {
            doDFSvisit(i);
        }
    }
}
void doDFSvisit(int node)
{
    int i;
    time=time+1;
    Distance[node]=time;
    color[node]="grey";
    for(i=1; i<=vertex; i++)
    {
        if(adjacency_matrix[node][i]==1)
        {
            if(color[i]=="white")
            {
                parent[i]=node;
                doDFSvisit(i);
            }
        }
    }
    color[node]="black";
    //extra line for result
    result.push(node);
    //cout<<"Pushed : "<<node<<endl;
    //
    time=time+1;
    Finishing_time[node]=time;
}
void printTSpath()
{
    cout<<"Topologically Sorted Path (after DFS) :"<<endl;
    int i,counter=1;
    //cout<<"Stack size : "<<result.size()<<endl;
    //int stackSize = result.size();
    for(i=1; i<=vertex; i++)
    {
        cout<<result.top()<<" -> ";
        tSVertex[counter]=result.top();
        counter++;
        result.pop();
    }
    cout<<" End"<<endl;
}
void Initialize_Single_Source()
{
    cout<<"Enter source : ";
    cin>>source;
    int i;
    for(i=1; i<=vertex; i++)
    {
        cost[i]=999999;
        parent[i]=0;
        //extra line
        visited[i]=0;
    }
    cost[source]=0;
}
void relax(int u,int v)
{
    if( cost[v]> (cost[u]+weight_matrix[u][v]))
    {
        cost[v]=(cost[u]+weight_matrix[u][v]);
        parent[v]=u;
    }
}
void DAG()
{
    int i,j,k,counter=1;
    for(i=1;i<=vertex;i++)
    {
        int node = tSVertex[counter];
        for(j=1;j<=vertex;j++)
        {
            if(adjacency_matrix[node][j]==1)
            {
                relax(node,j);
            }
        }
        counter++;
    }
}
void printCostAndPath()
{
    int i;
    for(i=1; i<=vertex; i++)
    {
        cout<<"For node "<<i<<" : "<<endl;
        if(cost[i]>=999999)
        {
            cout<<"Cost : "<<"Infinity"<<endl;
        }
        else
        {
            cout<<"Cost : "<<cost[i]<<endl;
        }
        cout<<"Path : End <- "<<i<<" <- ";
        int l = parent[i];
        while(true)
        {
            if(l==source||l==0)
            {
                if(l==source)
                {
                    cout<<l<<" <- ";
                }
                break;
            }
            else
            {
                cout<<l<<" <- ";
                l=parent[l];

            }
        }
        cout<<" Start"<<endl;

    }

    //for minimum cost
    int minCost = 999999;
    int nodeSaver;
    for(i=1; i<=vertex; i++)
    {
        // do not count if it is source node
        if(i!=source)
        {
            if(cost[i]<minCost)
            {
                minCost=cost[i];
                nodeSaver=i;
            }
        }
    }
    cout<<"From source node the minimum cost (without source node) is : "<<endl;
    cout<<"Node number : "<<nodeSaver<<endl;
    cout<<"Cost : "<<minCost<<endl;
    cout<<"Path : End <- "<<nodeSaver<<" <- ";
    int l = parent[nodeSaver];
    while(true)
    {
        if(l==source||l==0)
        {
            if(l==source)
            {
                cout<<l<<" <- ";
                break;
            }
        }
        else
        {
            cout<<l<<" <- ";
            l=parent[l];

        }
    }
    cout<<" Start"<<endl;
}
/*
input:
6
10
1 2
5
2 3
2
3 4
7
4 5
-1
5 6
-2
2 4
6
4 6
1
1 3
3
3 5
4
3 6
2
*/