Bellman-Ford (OWN)

//note : do not use INT_MAX for comparison,use a big number (i.e. : 999999) instead
#include<iostream>
using namespace std;

int vertex,edge,source;
int adjacency_matrix[100][100],weight_matrix[100][100];
int parent[100],cost[100],visited[100];

void inputGraph();
void Initialize_Single_Source();
//int Extract_Min();
void relax();
int BellmanFord();
void printCostAndPath(int);

int main(void)
{
    inputGraph();
    Initialize_Single_Source();
    int i = BellmanFord();
    printCostAndPath(i);
    return 0;
}
void inputGraph()
{
    cout<<"Total vertex : ";
    cin>>vertex;
    cout<<"Total edge   : ";
    cin>>edge;
    int i,j;
    //make all weight infinity
    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            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 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;
}
/*
int Extract_Min()
{
    int minimumCost = 999999;
    int i=0,saveNode=0;
    for(i=1; i<=vertex; i++)
    {
        if(visited[i]==0)
        {
            if(cost[i]<minimumCost)
            {
                minimumCost=cost[i];
                saveNode=i;
            }
        }
    }
    visited[saveNode]=1;
    return saveNode;
}
*/
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;
    }
}
int BellmanFord()
{
    int i,j,totalVertex=1;;
    while(totalVertex<=vertex)
    {
        //int minCost = Extract_Min();
        for(i=1; i<=vertex; i++)
        {
            for(j=1; j<=vertex; j++)
            {
                if(adjacency_matrix[i][j]==1)
                {
                    relax(i,j);
                }
            }
        }
        totalVertex++;
    }
    int m,n;
    int flag=1;
    for(m=1; m<=vertex; m++)
    {
        for(n=1; n<=vertex; n++)
        {
            if(adjacency_matrix[m][n]==1)
            {
                if(cost[m]+weight_matrix[m][n]<cost[n])
                {
                    flag=0;
                }
            }
        }
    }
    if(flag==1)
    {
        //cout<<"True"<<endl;
        return 1;
    }
    else if(flag==0)
    {
        //cout<<"False"<<endl;
        return 0;
    }
}
void printCostAndPath(int isPossible)
{
    if(isPossible==1)
    {
        cout<<"Bellman ford is possible for this graph"<<endl;
        int i;
        for(i=1; i<=vertex; i++)
        {
            cout<<"For node "<<i<<" : "<<endl;
            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;
    }
    else if(isPossible==0)
    {
        cout<<"Bellman Ford is not possible for this graph"<<endl;
    }
}
/*
input:
5
10
1 2
6
1 5
7
2 3
5
2 4
-4
2 5
8
3 2
-2
4 1
2
4 4
7
5 3
-3
5 4
9
*/