Bellman-Ford 1

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<limits.h>

int edge,vertex,source,top=-1;
int adjacency_matrix[100][100],weight_matrix[100][100];
int parent[100],cost[100],stack[100];

void push(int);
int pop();
int isEmptyStack();
void inputGraph();
void inputSource();
void initilizeSingleSource(int);
void relax(int,int);
bool bellmanFord(int);
void printCostAndPath(bool);

int main(void)
{
    inputGraph();
    inputSource();
    bool isPossible = bellmanFord(source);
    printCostAndPath(isPossible);
    return 0;
}

void push(int node)
{
    stack[++top]=node;
}
int pop()
{
    return stack[top--];
}
int isEmptyStack()
{
    if(top==-1)
    {
        return 1;
    }
    return 0;
}
void inputGraph()
{
    printf("Enter total vertex : ");
    scanf("%d",&vertex);
    printf("Enter total edge   : ");
    scanf("%d",&edge);
    int i,j,start,end;
    for(i=1; i<=edge; i++)
    {
        printf("Enter edges %d 's start and end vertex : ",i);
        scanf("%d %d",&start,&end);
        // optional edit needed : this is for non - directed graph
        // so both [start][end] = [end][start] = 1 double assign
        // scan for each vertex separately
        adjacency_matrix[start][end]=1;
        //adjacency_matrix[end][start]=1;
        printf("Enter weight for edge %d : ",i);
        scanf("%d",&weight_matrix[start][end]);
        //edit needed : add this line
        //weight_matrix[end][start] = weight_matrix[start][end]
    }
    printf("Adjacency matrix : \n");
    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            printf("%d ",adjacency_matrix[i][j]);
        }
        printf("\n");
    }
    printf("Weight matrix : \n");
    for(i=1; i<=vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            printf("%d ",weight_matrix[i][j]);
        }
        printf("\n");
    }
}
void inputSource()
{
    //edit needed : this code does not work if source is not 1
    printf("\nEnter source node (1 to %d) : ",vertex);
    scanf("%d", &source);
}
void initilizeSingleSource(int Source)
{
    int j;
    for(j=1; j<=vertex; j++)
    {
        parent[j]=0;
        cost[j]=999999;
    }
    cost[Source]=0;
}
void relax(int u,int v)
{
    if(cost[u]+ weight_matrix[u][v]<cost[v])
    {
        cost[v] = cost[u] + weight_matrix[u][v];
        parent[v] = u;
    }
}
bool bellmanFord(int sourceNode)
{
    int i,j,k;
    initilizeSingleSource(sourceNode);
    for(i=1; i<vertex; i++)
    {
        for(j=1; j<=vertex; j++)
        {
            for(k=1; k<=vertex; k++)
            {
                // !=0
                if(adjacency_matrix[j][k])
                {
                    relax(j,k);
                }
            }
        }
    }

    for(j=1; j<=vertex; j++)
    {
        for(k=1; k<=vertex; k++)
        {
            // !=0
            if(adjacency_matrix[j][k])
            {
                if(cost[j]+weight_matrix[j][k]<cost[k])
                {
                    return false;
                }
            }
        }
    }
    return true;
}

void printCostAndPath(bool possibleOrNot)
{
    if(possibleOrNot==true)
    {
        int i;
        printf("\nBellman Ford function returns 'True'\n");
        printf("Cost       : Path\n");
        for(i=1; i<=vertex; i++)
        {

            if(cost[i]<999999)
                printf("%d          : ",cost[i]);
            else
                printf("\nInfinity\n:");
            push(i);
            while(stack[top]!=0)
            {
                push(parent[stack[top]]);
            }
            while(!isEmptyStack())
            {
                if(stack[top]!=0)
                    printf("%d -> ",stack[top]);
                pop();
            }
            printf("End!\n");
        }
    }
    else
    {
        printf("\nBellman Ford function returns 'False'\n");
        printf("This Graph has no shortest path\n");
    }
}