[shkola] dijkstra & floyd

Prashtam vi koda na dvata algorityma (ne che gi nqma vyv vsqka kniga, no
vse pak).

Shte vi pratq i dijkstra s piramida v blizko bydeshte (v momenta malko me e
myrzel).

A shte vi namerq i malko zadachki za domashno, no i tova posle ;-)

-- 
Rangel Dokov



#include <stdio.h>

// maksimalniq broj vyrhove v grafa
#define MAXN    100

// tova trqbva da e po-golqmo ot dylzhinata na naj-dylgiq (prost) pyt
// v grafa
#define INF     2000000l

// matrica na sysedstvo opisvashta grafa
// v kletka adj[i][j] stoi cenata na pytq ot `i' do `j'
int adj[MAXN][MAXN];

// broj na vyrhovete v graf-a
int n;

// raztoqnieto ot nachalniq vryh do vseki drug
int dist[MAXN];
// spisak na posetenite
int visited[MAXN];

int parent[MAXN]; // optional

void dijkstra (int s) {
        int i, min;

        // inicializaciq na raztoqniqta
        for (i = 0; i < n; i++)
                dist[i] = INF;

        // slagame nachalniq vryh
        dist[s] = 0;
        min = 0;

        while (1) {
                // namirame naj-blizkiq vryh kojto ne e bil poseten
                for (i = 0; i < n; i++)
                        if ((visited[min]) ||
                            (!visited[i] && dist[i] <dist[min]))
                                min = i;

                // tova pokazva che ne sme namerili neposeten vryh
                // t.e. kraj
                if (visited[min])
                        break;

                // `poseshtavame' vyrha i presmqtame novite raztoqnie
                visited[min] = 1;
                for (i = 0; i < n; i++)
                        if (adj[min][i] && (dist[min]+adj[min][i] < dist[i])) {
                                dist[i] = dist[min] + adj[min][i];
                                parent[i] = min; //optional
                        }
        }
}

/*

vhoden fajl:
pyrvi red: N E (syotvetno broj vyrhove i broj rebra)
oshte E reda s opisanie na rebrata - nachalen vryh, kraen vryh, cena
 
primer:
        3 3
        1 2 5
        1 3 10
        2 3 3
*/

void read_data() {
        int s, t, c, e;

        scanf ("%d%d", &n, &e);
        while (e-- > 0) {
                scanf("%d%d%d", &s, &t, &c);
                s--; t--;
                adj[s][t] = c;
                adj[t][s] = c; // tova go nqma ako grafa e orientiran
        }
}

void print_dist() {
        int i;

        for (i = 0; i < n; i++)
                printf("distance to node %d is %d\n", i, dist[i]);
}

int main() {
        read_data();
        dijkstra (0);
        print_dist();
        return 0;
}

// za malko poveche obqsneniq vizhte dijsktra.c
#include <stdio.h>

#define MAXN    100
#define INF     2000000l

int adj[MAXN][MAXN];
int n;

// v tova se zapisvat raztoqniqta mezhdu vseki 2 vyrha
int dist[MAXN][MAXN];

void floyd() {
        int i, j, k;

        // inicializaciq na dylzhinite
        for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++)
                        // razchitam che ako nqma rebro cenata e 0
                        // t.e. 0 e nevalidna cena
                        // mozhe da se smeni na -1, no togava shte trqbva
                        // da se inicializira matricata na sysedstvo
                        if (adj[i][j] > 0)
                                dist[i][j] = adj[i][j];
                        else
                                dist[i][j] = INF;
                dist[i][i] = 0;
        }

        // tova si e samiq floyd
        // razpolozhenieto na ciklite _ima_ znachenie
        for (k = 0; k < n; k++)
                for (i = 0; i < n; i++)
                        for (j = 0; j < n; j++)
                                if (dist[i][k] + dist[k][j] < dist[i][j])
                                        dist[i][j] = dist[i][k] + dist[k][j];
}

// za formata na vhoda vizh dijkstra.c
void read_data() {
        int s, t, c, e;

        scanf ("%d%d", &n, &e);
        while (e-- > 0) {
                scanf ("%d%d%d", &s, &t, &c);
                s--; t--;
                adj[s][t] = c;
                adj[t][s] = c;
        }
}

void print_dist() {
        int i, j;

        printf ("Distances are:\n\n");
        for (i = 0; i < n; i++) {
                printf ("%d", dist[i][0]);
                for (j = 1; j < n; j++)
                        printf (" %d", dist[i][j]);

                printf ("\n");
        }
}

int main () {
        read_data();
        floyd();
        print_dist();
        return 0;
}

Other related posts: