009 Algoritmul lui Dijkstra

[•filipb]

Aici puteţi discuta despre problema Algoritmul lui Dijkstra.

[•byndrsn]

O varianta dragutza a algoritmului lui Dijkstra foloseste "buckets" in loc de heaps si merge foarte bine in practica. Nu imi amintesc exact daca are un nume, cred ca e cunoscut ca Dial's implementation of Dijkstra's algorithm. Algoritmul e foarte simplu si foloseste cateva idei dragutze care s-ar putea sa fie utile.

Pot sa schitzez algoritmul daca starneste interesul cuiva .

Later edit:

Dial's algorithm - varianta naiva:

Algoritmul lui Dial difera de algoritmul lui Dijkstra prin metoda in care selecteaza nodul cu distantza temporara minima la fiecare pas. Fie C lungimea maxima a unei muchii in G. Algoritmul mentine nC + 1 buckets numerotate de la 0 la nC: in bucket k se afla toate nodurile cu distantza temporara egala cu k (orice distantza temporara finita este cel mult nC). 

Pentru a selecta nodul cu distantza temporara minima, scanam buckets 0, 1, ... pana intalnim primul bucket k care nu e gol (fiecare nod din bucket k este un nod cu distanza temporara minima). Pentru fiecare nod v din bucket k, stergem v din bucket, marcam distantza lui v ca permanenta si modificam distantele vecinilor lui v (daca e necesar). Cand distantza unui nod v este schimbata de la d_1 la d_2, mutam v din bucket d_1 in bucket d_2 (daca d_1 este infinit, v intra in bucket d_2). La urmatorul pas, vom rezuma scanarea incepand de la bucket k + 1. Algoritmul merge pentru ca distantzele marcate ca permanente in algoritmul lui Dijkstra sunt non-decreasing. Buckets pot fi implementate folosind liste dublu inlantuite (ca sa obtinem O(1) pentru fiecare operatie necesara: verifica daca un bucket e gol, sterge un element din bucket, adauga un element in bucket).

Worst-case running time e O(m + nC) care e nu e polinomial, dar algoritmul e foarte rapid in practica.  Spatiul necesar e O(nC), dar se poate mult mai bine. E suficient sa mentinem doar C + 1 buckets. Buckets sunt numerotate de la 0 la C si un nod v cu distantza finita d(v) este in bucket d(v) mod(C + 1). Aceasta varianta se bazeaza pe urmatoarea observatie: daca un nod u a primit o distantza permanenta la inceputul unei iteratii a algoritmului lui Dijkstra, toate nodurile v cu distantza temporara finita satisfac d(v) <= d(u) + C la sfarsitul iteratiei. Asa ca in orice moment un anumit bucket contine doar noduri cu aceeasi distantza (in plus, daca un nod cu distantza minima e in bucket k, buckets k + 1, k + 2,  ..., C, 0, 1, ..., k - 1 contin noduri cu distantza din ce in ce mai mare).

Mai sunt doua idei dragutze (Dial's implementation cu "bounded-width buckets" si "multi-level buckets") pe care poate o sa le scriu in curand.

Se pare ca ia 100 (cam la limita pe ultimul test) (http://infoarena.ro/job_detail/144869)

Un mic articol despre Dial's algorithm and variations o sa apara aici: http://infoarena.ro/dijkstra-buckets
 

[•wefgef]

Posteaza-l te rog. M-ai facut curios.

[•Cosmin]

wefgef: nu mai stii problema car? exact chestia asta faci: tii liste pentru costuri fixate.

La asta ma refeream cand am pus in training-path (http://infoarena.ro/training-path) dijkstra cu costuri mici.

[•byndrsn]

Era postat pe site deja? Oops, ar trebui sa ma uit mai atent in viitor  .

[•Cosmin]

E doar o solutie a unei probleme din concurs unde costurile sunt 0, 1, 2, 3, nu o explicatie detaliata a algoritmului general.

Uite un articol in ginfo despre acelasi algoritm: http://www.ginfo.ro/revista/13_6/focus2.pdf

[•wefgef]

wefgef: nu mai stii problema car? exact chestia asta faci: tii liste pentru costuri fixate.

La asta ma refeream cand am pus in training-path (http://infoarena.ro/training-path) dijkstra cu costuri mici.

Nu stiam ca asta e numele algoritmului .

[•Cosmin]

@byndsr poti baga descrierea ce ai facut-o in un articol scurt si cu link spre problema asta si implementarea ta si spre problema car. Infoarena e wiki deci poti sa contribui usor si algoritmul e misto sa fie mentionat.

[•Prostu]

O alta implementare care ia 100 de puncte este folosind priority_queue din STL. Daca imi amintesc bine, Cosmin ii spunea lazy detection.
La problema asta am observat din nou, cat de rapide sunt streamurile din g++ 4.2. Folosind functiile standard iau 90 de puncte, pentru ca ultimul test iese din timp. Folosind insa streamurile, ultimul test intra in aprox 450 ms.

Nu stiu ce nume are. Bellman-Ford cu coada, din cate stiu se numeste Bellman-Kalaba. Poate are si el un nume de care nu am auzit inca. Nu auzisem nici numele de Dial, desi am folosit in mai multe probleme BFS/Bellman-Ford cu cozi pentru fiecare cost.

[•blasterz]

Eu as spune ca e un Bellman-Ford cu priority_queue :-"... e exact ca bellman-ford cu coada numai ca in loc de coada e folosit un heap

[•bogdan2412]

Pai atunci Dijkstra in sine e Bellman-Ford cu Set / Heap... Dijkstra se bazeaza pe ideea de a extrage minimul la fiecare pas si a scoate nodul acela din graf... Bellman-Ford cu sau fara coada se bazeaza pe faptul ca dupa N relaxari a tuturor muchiilor distantele minime sunt calculate...

[•the1dragon]

o alta varianta de implementare: in loc de heap folosim un arbore de intervale. mi se pare putin mai scurta implementarea.

[•cosser]

 ce face un heap in algoritmul lui dijkstra? e o coada cu prioritate? apropo credeti ca e mai bun un heapsort decat un quicksort?

[•filipb]

Algoritmul lui Dijkstra alege la fiecare pas nodul inca neales de cost minim. Daca tu mentii un vector, va trebui de fiecare data sa parcurgi tot vectorul pentru a vedea care este acest nod, si asta se poate dovedi ineficient. Daca vrei sa faci mai bine, trebuie sa gasesti o structura de date care sa poata extrage minimul si modifica valoarea unui element/sterge un element in O(1) sau O(logN). Aceasta structura poate fi un heap.
Astfel, cand aplici algoritmul lui dijkstra, ca sa afli care este nodul de cost minim inca neales interoghezi heapul in complexitate O(1). Ai aflat acest nod si il stergi din heap, cu complexitate O(logN). Apoi relaxezi toate muchiile din nodul curent, care inseamna sa modifici valoarea costului unui nod in heap, care se realizeaza tot cu complexitate O(logN).
Complexitatea finala va fi O(M log N), care, daca graful este rar, este mult mai buna decat O(N^2).

[•wefgef]

ce face un heap in algoritmul lui dijkstra? e o coada cu prioritate? apropo credeti ca e mai bun un heapsort decat un quicksort?

Un heap este intr-adevar o coada de prioritate.

Quicksort e mai bun decat heapsort si e si mai scurta implementarea.

[•hitmann]

cred ca s-au reavaluat sursele aveam 100 si acum vad ca am 90, oricum m-am chinuit si prima oara sa obtin 100, acuma nu am idei inafara faptul ca eu cred ca folosesc prea mult memorie fapt ce imi incetineste executia.
am declarat :

Cod:

 const
pinfinit=maxlongint;
type long=1..50000;
     pnod=^nod;
     nod=record
         nod:long;
         i:0..1000;
         urm:pnod;
         end;
     cheie=record
           val:longint;
           poz:long;
           end;
     vec=array[1..50000]of long;
var a:array[1..50000]of pnod;
    d:array[1..50000]of record
                        d:longint;
                        s:0..1;
                        end;
    id:^vec;
    h:array[1..50000]of cheie;
    i,poz,n,m,dheap,he,min:longint;
    p:pnod;
    ok:boolean;
    g:text;
 

 A - lista muchiilor
 D- distanta minima pana la fiecare nod si un alt camp care retine daca nodul mai este sau nu in coada ( initial aveam 2 vectori distincti dar am constatat cu uimire ca daca declar un singur vector de inregistrari cu 2 campuri, programul ruleaza mai repede desi nu inteleg de ce)
 H - heapul
 ID - vector auxiliar pt operatiile in heap
Cu ce ma complic ca nu imi dau seama ? (ies din timp la ultimul test)

[•domino]

ce face un heap in algoritmul lui dijkstra? e o coada cu prioritate? apropo credeti ca e mai bun un heapsort decat un quicksort?

Un heap este intr-adevar o coada de prioritate.

Quicksort e mai bun decat heapsort si e si mai scurta implementarea.

Un heap nu este o coada de prioritate. Poti implementa o coada de prioritate folosind un heap, dar o coada de prioritate este o structura de date abstracta (http://en.wikipedia.org/wiki/Abstract_data_type).

[•cosser]

dijkstra cu heap e mai bun intr-un graf cu costuri pozitive,decat bellman ford cu coada?
 iar oftopic, pentru arborele partial de cost minim, algoritmul lui prim este mai eficient decat altii?

[•wefgef]

Dijkstra cu heapuri are complexitatea mai buna, deci ar trebui sa fie mai rapid, insa bellman ford se implementeaza mai rapid .

Pentru APM, eu folosesc Kruskal, tot datorita implementarii mult mai simple. Teoretic, Prim este mai bun.

[•cosser]

OK mersi

[•Cosmin]

Kruskal e O(m log m + m log* n) daca folosesti structuri de multimi disjuncte. Daca il implementezi tzaraneste are O(m log m + n^2).

Algoritmul lui Prim daca il implementezi ca in manual are complexitate O(n^3), daca il implementezi dupa cum se sugereaza in cormen ajungi la O(n^2) sau O(m log n) daca folosesti heapuri.

Se merita sa folosesti Prim in loc de Kruskal cand graful e dens. Eu am primit la o finala agora o problema unde trebuia sa determini arborele partial de cost minim pentru un graf dat de niste puncte in plan. In cazul asta algoritmul lui Prim are complexitate O(n^2) pe cand cel a lui Kruskal are O(n^2 log n), si asta era diferenta intre 100 si 40 de puncte.

Pentru curiosi, arborele partial de cost minm intr-un graf de genul asta se poate determina in complexitate O(n) dar acest rezultat este unul teoretic. Alta observatie misto este ca muchiile din arborele partial de cost minim in graful de care am vorbit apartin triangularizarii Delaunay care se poate determina in timp O(n log n) si are cel mult 3n - 6 muchii.

[•wefgef]

http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree

S-a gasit O(N)?

[•Cosmin]

Vorbeam prostii, dar exista un algoritm randomizat ce gaseste arborele partial de cost minim al unui graf in O(m). Pentru grafuri planare intr-adevar algoritmul e O(n log n).

[•byndrsn]

Pentru grafuri planare, cel mai bun algoritm deterministic e O(n) (Cheriton-Tarjan). Pentru grafuri generale, cel mai bun algoritm deterministic e O(m alpha(n, m)) (alpha -- inverse Ackerman function) (Chazelle).

[•toni2007]

eu cu Bellman Ford iau doar 40 (3 TLE si 3 SIGSEGV) se poate implementa BF pt 100 ?