Algorithm/bellmanFord.c at master · secretcoder021714/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <limits.h>
#define INF 40000

void input(void);
void bf(void);
void print(void);


int v,adj[20][20],weight[20],start;

void bf(void)
{
    printf("\nEnter the starting node : ");
    scanf("%d",&start);
    weight[start] = 0;

    for(int k = 0 ; k < v-1 ; k++)
    {
        for(int i = 0 ; i < v ; i++)
        {
            for(int j = 0 ; j < v ; j++)
            {
                if(adj[i][j]!=0 && adj[i][j]+weight[i] < weight[j])
                {   weight[j] = adj[i][j]+weight[i];
                    //printf("\n%d %d %d",weight[j],adj[i][j],weight[i]);
                    //print();
                }
            }
        }
    }

    for(int i = 0 ; i < v ; i++)
    {
        for(int j = 0 ; j < v ; j++)
        {
            if(adj[i][j]!=0 && adj[i][j]+weight[i] < weight[j])
                printf("\nGraph contains negative weight cycle!");
        }
    }

}

void input(void)
{
    printf("\nEnter the adjacency matrix :\n");
    for(int i = 0;i < v ; i++)
    {
        for(int j = 0 ; j < v ; j++)
            scanf("%d",&adj[i][j]);
        weight[i] = INF;
    }
}

void print(void)
{
    printf("\nAll paths from starting vertex(%d) : ",start);
    for(int i = 0 ; i < v ; i++)
    {
        if(weight[i]>=INF)
            printf("INF ");
        else
            printf("%d ",weight[i]);
    }
}

int min(int a , int b)
{
    return a<b ? a : b;
}

int main()
{
    printf("\nEnter no of vertices : ");
    scanf("%d",&v);
    input();
    bf();
    print();
    return 0;
}

/*

0 -1 4 0 0
0 0 3 2 2
0 0 0 0 0
0 1 5 0 0
0 0 0 -3 0

*/