Bellman-Ford Algorithm

 avatar
user_3763047219
c_cpp
2 years ago
1.6 kB
4
Indexable
Never
#include <iostream>

int main()
{
    int n = 0, m = 0, s = 0;
    scanf("%d %d", &n, &m);
    int weight[201][3] = {};
    int key[201] = {};
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &weight[i][0], &weight[i][1], &weight[i][2]);
    }

    for (int i = 1; i <= n; i++) {
        key[i] = 10001;
    }
    scanf("%d", &s);
    key[s] = 0;
    int count = 1;
    int v[201] = { 0 };
    int parent[201] = { 0 };
    v[s] = 1;
    while (count < n) {
        int eachkey = 10001;
        for (int i = 1; i <= m; i++) {
            if (key[weight[i][1]] > weight[i][2] + key[weight[i][0]]) {
                key[weight[i][1]] = weight[i][2] + key[weight[i][0]];
                parent[weight[i][1]] = weight[i][0];
            }
        }
        count = count + 1;
    }
    int sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++) {
        sum1 = sum1 + key[i];
    }
    for (int i = 1; i <= m; i++) {
        if (key[weight[i][1]] > weight[i][2] + key[weight[i][0]]) {
            key[weight[i][1]] = weight[i][2] + key[weight[i][0]];
            parent[weight[i][1]] = weight[i][0];
        }
    }
    for (int i = 1; i <= n; i++) {
        sum2 = sum2 + key[i];
    }
    if (sum1 != sum2) {
        printf("There is a negative weight cycle in the graph");
    }
    else {
        for (int i = 1; i < n; i++) {
            printf("%d ", key[i]);
        }
        printf("%d\n", key[n]);

        for (int i = 1; i < n; i++) {
            printf("%d ", parent[i]);
        }
        printf("%d", parent[n]);
    }
}