演算法 Bellman-Ford Algorithm

 avatar
user_6817964
c_cpp
a year ago
1.8 kB
2
Indexable
Never
int main()
{
    int n, m, i[201], j[201], w[201], s;
    scanf("%d%d", &n, &m);
    for (int k = 1; k <= m; k++) {
        scanf("%d%d%d", &i[k], &j[k], &w[k]);
    }
    scanf("%d", &s);

    int key[51], parent[51], finish[51], ok = 0;
    for (int k = 1; k <= n; k++) {
        key[k] = 99999;
        parent[k] = 0;
        finish[k] = 0;
    }
    key[s] = 0;

    int s_ori = s;

    while (ok != n) {
        int min = 99999;
        for (int k = 1; k <= n; k++) {
            if (key[k] < min && finish[k] == 0) {
                min = key[k];
                s = k;
            }
        }
        finish[s] = 1;

        for (int k = 1; k <= m; k++) {                       //比第二題多刪掉finish
            if (s == i[k] && key[j[k]] > (w[k] + key[s])) {
                key[j[k]] = w[k] + key[s];  // 比第一題多改這
                parent[j[k]] = s;
            }
        }
        ok++;
    }

    s = s_ori;
    ok = 0;
    int circle = 0;
    while (ok != n) {
        int min = 99999;
        for (int k = 1; k <= n; k++) {
            if (key[k] < min && finish[k] == 0) {
                min = key[k];
                s = k;
            }
        }
        finish[s] = 1;

        for (int k = 1; k <= m; k++) {                       
            if (s == i[k] && key[j[k]] > (w[k] + key[s])) {
                printf("There is a negative weight cycle in the graph");
                circle = 1;
                ok = n - 1;
            }
        }
        ok++;
    }

    if (circle == 0) {
        printf("%d", key[1]);
        for (int k = 2; k <= n; k++) {
            printf(" %d", key[k]);
        }
        printf("\n%d", parent[1]);
        for (int k = 2; k <= n; k++) {
            printf(" %d", parent[k]);
        }
    }
}