[shkola] dijkstra s heap

Mislq che malko se poomazah s komentarite, no nishto. Te ne vredqt ;-)

P.S. Boqne vizh http://99-bottles-of-beer.ls-la.net/

Tova go prashtam tuk ponezhe onezi kreteni ot mail.bg sa reshili da blokirat
vsqkakva poshta idvashta ot mail.dir.bg (ponezhe bila spam ;-). Ne znam koga
tiq nekadyrnici shte prestanat s ciganskite si nomera, no maj nqma da e skoro.

P.P.S. ako reshite da prashtate flame do root/postmaster/support/abuse@xxxxxxx
dobavete malko i ot moe ime ;-)

-- 
Rangel Dokov
#include <stdio.h>

#define MAXN    100
#define INF     2000000l

// tova maj raboti samo s GCC, taka che ako polzvate drug
// kompilator shte trqbva da go smenite s dolnoto
// (izpolzvam extension kym ezika C, kojto mi pozvolqva da
// da deklariram block-scope variables, koeto po-princip
// go ima v C++ chak ;-)
#define swap(a,b) {int tmp; tmp = a; a = b; b = tmp;}

// a tova raboti samo za celi chisla ;-)
// no v sluchaq vyrshi rabota
//#define swap(a,b) a ^= b, b ^= a, a ^= b;

/*
izpolzvam spisyci na sysedstvo ponezhe inache prosto nqma smisyl
ot tova da se izpolzva piramida. Ako izpolzvate matrica na
sysedstvo taka ili inache slozhnostta vi stava O(n*n).
samo che namalqte malko konstantite ponezhe:
standartna dijkstra s linejno namirane na naj-blizkiq vryh e
priblizitelno 2*N*N
ako se slozhi piramida (no s matrica na sysedstvo) stava
priblizitelno N*N + N*log(N)
za koeto v obshtiq sluchaj ne vi pomaga mnogo ponezhe
onzi N*log(N) e s visoki konstanti ot piramidata
i taka se stiga do spisyk na sysedstvo pri kojto slozhnostta stava
mnogo gadna za opredelqne i chestno kazano ne moga da q smetna.
no v sredniq sluchaj trqbva da e _dosta_ po-dobra ot gornite 2
varianta. Tova deto go pishe po knigite N*log(E) sega kato se
opitah da smqtam slozhnost mi izglezhda kato nqkakva fikciq ;-)
no mozhe pyk i da e vqrno.
naj-dobroto mi predpolozhenie obache e O(N*log(N) + E)
koeto pri pylen graf otnovo se svezhda do O(N*N), no v obshtiq
sluchaj e dosta po-dobre
*/
int nlist[MAXN][MAXN];

// a tova mi e matricata na sysedstvo koqto vypreki vsichko mi trqbva ;-)
int cost[MAXN][MAXN];

// broj na vyrhovete
int n;

// naj-kratkite rastoqniq namereni ot dijkstrata
int dist[MAXN];
// dali daden vryh e bih poseten
int visited[MAXN];

// tova mi e piramidata.
// heap[0] sydyrzha broq na elementite v piramidata plus 1
// t.e. sochi kym `sled-posledniq' element na piramidata
int heap[MAXN];

// v tozi masiv za vseki vryh trqbva da si pazq negovata poziciq
// v piramidata. Taka kogato promenq raztoqnieto do nqkoj vryh
// znam tezhesta na koj element v piramidata se e promenila i
// che trqbva syotvetno da go premestq nagore
int pos[MAXN];

// incializaciq na piramidata
void heap_init() {
        heap[0] = 1;
}

// tova se izpolzva ot piramidata za da sravni 2 elementa i ponzhe
// v piramidata pazq nomera na vyrhove tova neshto sravnqva raztoqniqta
// na syotvetnite vyrhove
// vryshta <0 ako `a' e po-blizo
// >0 ako `b' e po-blizo i 0 kogato sa ravni
//
// ako kompilatora vi ne poddyrzha `inline' proceduri e naj-dobre da
// si inline-nete sami, ponezhe inache shte zabavi nenuzhno heap_*
// procedurite
// btw. mislq che gcc ignorira inline osven ako ne mu se dadat flogove
// za optimizaciq (e.g. `gcc -O2' ili `gcc -finline' v sluchaq)
inline int cmp(int a, int b) {
        return dist[a] - dist[b];
}

// izdiga elementa na poziciq `pos' v piramidata
// za celta se sravnqva s roditelq i t.n.
// NOTE: zabelezhete che pri izdiganeto na elementa se obnovqva i
// masiva `pos' kydeto sa zapisani poziciite na vyrhovete v
// piramidata
void shift_up(int p) {
        int c;

        c = p;
        while (c/2 > 0) {
                if (cmp(heap[c], heap[c/2]) < 0) {
                        swap(heap[c], heap[c/2]);
                        pos[heap[c]] = c;
                }
                c = c/2;
        }
        pos[heap[c]] = c;
}

// analogichno na gornata procedura samo che svalq element nadolu
// crez `if'-ovete se namira po-malkiq ot dvata sina i sled tova
// se proverqva dali toj mozhe da izmesti roditelq si
void shift_down(int p) {
        int c, t;

        c = p;
        while (c*2 < heap[0]) {
                if (c*2+1 < heap[0]) {
                        if (cmp(heap[c*2], heap[c*2+1]) < 0)
                                t = c*2;
                        else
                                t = c*2 + 1;
                } else
                        t = c*2;

                if (cmp(heap[c], heap[t]) > 0) {
                        swap(heap[c], heap[t]);
                        pos[heap[c]] = c;
                }

                c = t;
        }
        pos[heap[c]] = c;
}

// dobavq element v piramidata
void heap_push(int d) {
        int c;

        c = heap[0]++;
        heap[c] = d;
        pos[d] = c;
        shift_up(d);
}

// izvazhda element ot piramidata
int heap_pop() {
        int rv;

        rv = heap[1];
        pos[rv] = -1; // tova ne e neobhodimo, no pomaga pri debug
        heap[1] = heap[--heap[0]]; // ne go li obichate toq ezik ;-)

        if (heap[0] < 1) // tova shte reche che piramidata e prazna
                return -1;

        pos[heap[1]] = 1;
        shift_down (1);

        return rv;
}

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

        heap_init();

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

        // slagam vsichki vyrhove v piramidata
        for (i = 0; i < n; i++)
                heap_push(i);

        while ((c = heap_pop()) >= 0) {
                for (i = 1; i <= nlist[c][0]; i++)
                        if (dist[c]+cost[c][nlist[c][i]] < dist[nlist[c][i]]) {
                                dist[nlist[c][i]] =
                                        dist[c]+cost[c][nlist[c][i]];
                                shift_up (i);
                        }
        }
}

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--;

                // proverqvam dali rebroto veche ne mi e dadeno ponezhe
                // osven ako izrichno ne e kazano che rebrata ne se povtarqt
                // tova oznachava che zhurito shte mi dade edno i syshto
                // rebro 1000000000 pyti i shte mi skape spisycite na
                // sysedstvo po-dolu ;-)

                if (cost[s][t] > 0)
                        continue;

                cost[s][t] = c;
                cost[t][s] = c;

                nlist[s][++nlist[s][0]] = t;
                nlist[t][++nlist[t][0]] = s;
        }
}

void print_dist() {
        int i;

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

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

/*
P.S. ako i na systezanie izpishete 200 reda kod za edna programa da znaete
che ili ste prekalili s komentarite ili ste omazali reshenieto ;-)
*/

Other related posts: