Dijkstra Algorithm

 avatar
user_3763047219
c_cpp
2 years ago
1.4 kB
4
Indexable
Never
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 (weight[i][0] == s) {
                if (v[weight[i][1]] == 0) {
                    if (key[weight[i][1]] > weight[i][2]) {
                        key[weight[i][1]] = key[s] + weight[i][2];
                        parent[weight[i][1]] = s;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (v[i] == 0) {
                if (eachkey > key[i]) {
                    eachkey = key[i];
                    s = i;
                }
            }
        }
        v[s] = 1;
        count = count + 1;
    }

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