009 Algoritmul lui Dijkstra

[•Marius]

Am facut Dijkstra clasic si am luat 40pct. Imi poate explica cineva ce ar trebui sa fac cu heap-ul? Ca nu reusesc sa ma prind

Intuiesc ca avem nevoie de un min-heap la care sa tinem in varf dinstanta de la nodul sursa la cel mai apropiat nod, dar nu imi dau seama cum ar trebui manipulat.

Multumesc anticipat !

Fiecare nod din heap poate fi considerat ca o pereche (x, d), unde „x” reprezintă un nod din graf care se găseşte la distanţa „d” faţă de nodul sursă. Algoritmul lui Dijkstra presupune să obţii de „n-1” ori cel mai apropiat nod de sursă. Astfel, în vârful heapului ai cel mai apropiat nod de nodul sursă, dacă ţii heapul pe baza distanţelor. Extragi această pereche din vârful heapului, operaţie pe care o înveţi din manual dacă nu o ştii, după care relaxezi fiecare vecin al nodului tocmai obţinut. Se va întâmpla să relaxezi doar nodurile care încă mai sunt în heap, deoarece restul au distanţa mai mică iar muchiile au costuri pozitive. Când relaxezi un nod, acesta urcă în heap cât timp are o distanţă mai mică decât părintele său. E posibil să ajungă în vârf astfel. Repeţi procedeul.

[•alexandru92]

Am facut Dijkstra clasic si am luat 40pct. Imi poate explica cineva ce ar trebui sa fac cu heap-ul? Ca nu reusesc sa ma prind

Intuiesc ca avem nevoie de un min-heap la care sa tinem in varf dinstanta de la nodul sursa la cel mai apropiat nod, dar nu imi dau seama cum ar trebui manipulat.

Multumesc anticipat !

Faci exact ca la problema Heap

[•popoiu.george]

Multumesc Marius si alexandru pentru raspunsuri, am inteles rezolvarea, dar cu toate acestea iau 90pct. (WA pe testul 1)

Nu inteleg ce este gresit in sursa mea, desi am recitit-o de peste 10 ori.

Daca aveti timp sa aruncati o privire si sa vedeti ce este gresit as fi recunoscator, deoarece ma "sacaie" ideea de 90pct la o problema ce am impresia ca i-am inteles rezolvarea.

Sursa este comentata, asa ca nu ar trebui sa fie greu de inteles.

http://infoarena.ro/job_detail/388169?action=view-source

[•pauldb]

Accesul la testele problemelor din arhiva educationala este liber. Poti sa-ti downloadezi testul si sa vezi ce nu iti merge.

[•alexandru92]

Esti sigru ?
Chiar acum am downladat testul si am rulat sursa ta. In loc sa afiseze 10 la penultima valoare, pune 14. Fa un debug

[•popoiu.george]

Am rezolvat, chiar era un bug, merci Alexandru !

[•arnold23]

cu priority queue poate cineva sa obtine 100p?

[•Mishu91]

cu priority queue poate cineva sa obtine 100p?

Da. http://infoarena.ro/job_detail/357124

[•cezy]

Ma poatea ajuta si pe mine cineva sa iau 100 la sursa asta va rog    http://infoarena.ro/job_detail/401756?action=view-source
momentan imi iese din ultimul test dar nu stiu ce as putea sa-i mai fac

[•ooctav]

cod :

while(h.size() && pas<=1LL*n*m)

ce inseamna 1LL ?

[•mathboy]

Il pui pe 1 tip long long. E ca o conversie a inmultirii.

[•O_Neal]

merge si bellman ford varianta primitiva fara coada si nimic relaxezi muchii pana nu mai poti si iei 100 ! ironia sortii

[•gabitzish1]

Scopul problemei Algoritmul lui Dijkstra, e sa inveti algoritmul lui Dijkstra. 

[•O_Neal]

evident, am facut si eu cu multiset si am luat 80 si ma multumesc cu atat.. defapt nu inteleg de ce set-urile din STL iau mai putin adica de ce ar fi mai ineficiente, in fine, consider ca daca iei toate in considerare ( lungimea sursei, timpu necesar implementarii si rezultatele in sine ) atunci e mai bine la un concurs sa alegi sa implementezi cu STL pt ca e mai simplu si ai timp pt celelalte chestii sa zic asa, acuma depinde si asta, daca unu o implementat nush cate probleme cu heapuri facute manual, cred si eu ca nu o sa fol STL, dar pt altii optiunea e clara

[•alexandru92]

Un lucru ce are putea cauza ineficienta ar fi OOP. Poti folosi make_heap, pop_heap, push_heap, pentru a gestiona un heap.

[•O_Neal]

hm.. am facut folosind chestiile alea.. si am luat mai putin  adica am luat TLE la mai multe si nu cred ca am facut io gresit ceva adica am transformat sursa cu multiseturi intr-una folosind chestiile de care ziceai tu nimic altceva, lasa ca e bine si 80 cu multiseturi   

[•blasterz]

Ineficienta vine de la faptul ca set/multiset sunt implementat folosind Red-Black Trees, iar acestia au o constanta mult mai mare decat cea a unui heap. Cu functiile alea push_heap / pop_heap ar trebui sa poti lua 100.

[•Cosmin1490]

Am scris un Dijkstra normal, am luat 50 de puncte.
Am incercat apoi un Dijkstra cu heapuri, iese din timp la ultimul test si iau 90, iar in final cu un bellman cu coada si acelasi rezultat, iese din timp la ultimul test.
Probabil implementarea mea cu heapuri nu e optima.
Poate cineva sa arunce o privire si sa-mi dea un sfat?
[LE]
Am inteles unde gresesc la bellman, eu inserez nodul chiar daca este deja in coada,
dar la dijktra cu heapuri tot am intrebari.

[•BitOne]

Implementeaza push_down iterativ si apoi vezi ce se intampla

[•Cosmin1490]

aha... am sa incerc... ma gandeam ca motivu pt care pierd ceva timp e ca.. in bellman folosesc coada in stl.. in loc sa o implementez eu... iar in ambele cazuri.. reprezentarea grafului sub forma de vectori in stl.. si ma gandesc ca poate.. o reprezentare dinamica cu liste de adiacenta ar fi mai rapida

[•dornescuvlad]

Salut, m-am uitat eu peste sursa ta.Modificarea consta in faptul ca am folosit un vector<pair<int, int>> in loc de 2 vectori dinamici de dimensiune NMAX pentru a retine vecinii nodului, respectiv costul muchiei dintre acestia.
Am observat ca la inceput calculai si un numar de aparitii, desi nu e nevoie. (Am sters si portiunea aia de cod)
Uite sursa ta de 100 puncte :
http://infoarena.ro/job_detail/474034?action=view-source

[•Cosmin1490]

deci faptu ca retineam graful sub forma a doi vectori manca timpu.. si daca folosesc unul singur cu pair<> se rezolva.. multumesc mult pt timpu acordat
[LE] si partea cu numarul de aparitii pe care ai mentionat-o , din cate stiu n-am folosit nimic de genul acesta ... dar oricum.. acea modificare.. din 2 vectori cu unu pair... a rezolvat problema:D multumesc
[LE].. ahh am inteles . dar acea chestie care zici ca numara aparitiile era folosit p postul de un vector true false, desi era declarat int... era ceva memorie irosita ce-i drept.. dar l-am schimbat in unul bool

[•cosmyo]

Eu nu inteleg cum se ia 90 de pct cu 2 vectori separati din stl,iar cu un vector de pair<long,long> se ia 100.

[•Cosmin1490]

atunci cand tii unul pair faci o singura inserare pe muchie si nu doua ma gandesc eu.

[•PlayLikeNeverB4]

Ma tot chinuiam sa gasesc vreo optimizare la programul meu pentru ca luam 90 de puncte si la ultimul test depasea timpul. Dupa cam o ora de cautari printre sursele altora mi-am dat seama ca in mare sunt la fel. Am gasit solutia in final printr-o amarata comanda de settextbuf. Doar recent am auzit de aceasta de la alti membri printre comentarii, dar habar nu aveam ca poate sa faca o asemenea diferenta. In sfarsit 100!