belman_ford

#include<iostream>
#include<fstream>
#include<vector>
#define MAX_SIZE 3000
#define INF 999

typedef std::vector<int> vector;
vector vis;
vector g[MAX_SIZE];   //the graph stored in an adjacency matrix
int  n, m;    //n- no of vertices, m -no of edges
std::vector<std::pair<int,int>> dist;  //first to store the distance
                                        //second to store the parent
int source;
void read()
{
    std::ifstream in("file.txt");
    if (!in.is_open())
        std::cout << "Unable to open the file!\n";
    else
    {
        in >> source;
        int x, y, w;
        in >> n >> m;
        for (long long int i = 0; i < n; i++)
            g[i].assign(n, 0);

        for (long long int i = 0; i < m; i++)
        {
            in >> x >> y >> w;
            g[x][y] = w;
            //g[y][x] = w;
        }
    }
}
void init_dist()
{
    for (int i = 0; i < n; i++)
    {
        dist.push_back({ INF,-1 });
        //here NIL parent is -1
    }
}
int belman_ford(int source)
{
    int traverse;
    init_dist();
    dist[source] = { 0,-1 };
    for(int i=0;i<n;i++)
        for (int j = 0; j < n; j++)
        {
            traverse = 0;
            while (traverse < n)
            {
                if (dist[j].first != INF)
                {
                    //checking for relaxation
                    if (g[j][traverse]!=0 && dist[traverse].first > dist[j].first + g[j][traverse])
                    {
                        dist[traverse].first = dist[j].first + g[j][traverse];
                        dist[traverse].second = j;
                    }
                }
                ++traverse;
            }
        }
    //checking for negative cicles
    for (int i = 0; i < n; i++)
    {
        traverse = 0;
        while (traverse < n)
        {
            if (g[i][traverse]!=0 && dist[i].first+g[i][traverse] < dist[traverse].first)
            {
                return i;
            }
            ++traverse;
        }
    }
    return -1;
}

int main()
{
    read();
    int returned_value=belman_ford(source);
    if (returned_value != -1)
        std::cout << "there is negative cicle!\n";
    else
    {
        for (int i = 0; i < n; i++)
            std::cout << "node:" << i << " distance:" << dist[i].first << " parent:" << dist[i].second << "\n";

    }


    return 0;
}

/*


negative cycles
5 10
1 2 -1
1 3 2
1 4 4
2 1 2
2 3 1
3 4 5
3 5 1
4 3 -1
5 2 -3
5 4 4

without negative:

5 10
1 2 -1
1 3 2
1 4 4
2 1 2
2 3 3
3 4 5
3 5 3
4 3 -1
5 2 -3
5 4 4

*/