Bellman.cpp

#include <bits/stdc++.h>
using namespace std;
void bell(int edge[][3], int n, int m)
{

    int dis[n];
    for (int i = 0; i < n; i++)
        dis[i] = 100000;

    dis[0] = 0;
    for (int i = 1; i < n - 1; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int src = edge[j][0];
            int dest = edge[j][1];
            int w = edge[j][2];
            if (dis[src] != 100000 && dis[src] + w < dis[dest])
            {
                dis[dest] = dis[src] + w;
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << dis[i] << " ";

    // Step 3: detect negative cycle
    // if value changes then we have a negative cycle in the graph
    // and we cannot find the shortest distances
    for (int i = 0; i < m; i++)
    {
        int u = edge[i][0];
        int v = edge[i][1];
        int w = edge[i][2];
        if (dis[u] != 100000 && dis[u] + w < dis[v])
        {
            printf("Graph contains negative w cycle");
            return;
        }
    }
}
int main()
{
    int n, m; // vertex,edge
    cin >> n >> m;
    int edge[m][3];
    int s, d, w;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> edge[i][j];
        }
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cout << edge[i][j] << " ";
        }
        cout << endl;
    }

    bell(edge, n, m);
}