演算法 Dijkstra Algorithm

 avatar
user_6817964
c_cpp
3 years ago
1.1 kB
4
Indexable
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;

    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]) && finish[j[k]] == 0) {
                key[j[k]] = w[k] + key[s];  // 比第一題多改這
                parent[j[k]] = s;
            }
        }
        ok++;
    }

    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]);
    }

}
Editor is loading...