Dijkstra

[•Marius]

Am o problema cu implementarea algoritmului lui Dijkstra cu o coada de prioritati, adica cu un heap binar, pentru ca e singurul pe care il stiu (Fibonacci nu ). Mai precis, daca in coada de prioritati am nodurile si marginea superioara a costului minim, cum il pot gasi rapid (O(1) ?) ca sa il pot "relaxa". Dupa aceea este log V, asta stiu  .

Multumesc anticipat!

[•Marius]

Am gasit solutia !  Initial m-am gandit la pastrarea unui vector x[], unde x[i ] este pozitia in coada de prioritati a nodului i, dar nu reuseam sa il gasesc in coada cand avea valoarea infinit, putand fi in stanga sau in dreapta. Dar acum il construiesc de la zero, adica introduc nodul sursa si apoi, pe rand, daca nu au fost introduse celelalte noduri cu "relaxarea" de rigoare. 

Oricum, daca stie cineva o tehnica mai buna il rog sa imi spuna si mie! (Cred ca va spune mai multora!) 

[•filipb]

Mie cel mai simplu pentru Djikstra O(N log N) mi se pare cu arbore de intervale... ai un vector de lungime N in care retii distantele de la nodul sursa si un arbore de intervale: minimul pe intervalul respectiv in vector... si merge frumos... imi place mai mult decat sa fac heapurile.. bine, daca folosesti STL se merita sa faci heapuri pt. k e mult mai scurt.

Iar daca vrei cu heapuri, merge cu vectorul de pozitii care sa iti spuna pe ce pozitie in heap este nodul respectiv, iar cand faci sift sau percolate modifici si vectorul de pozitie pt. cele 2 noduri care se interschimba.
SPOR!

[•Marius]

Am reusit sa imi rezolv problema cu arborii de intervale!    Sunt incepator in din astea asa ca iti multumesc mult mult!

SPOR si tie Filip!  

[upthewall]

Nu mi-e obiceiul ca lucrez cu C++ STL de obicei, dar m-am bagat si am implementat o sursa pt Dijkstra in pascal folosind heapuri binare (ca in STL). E cam lung dar e bun pt a intelege ideea, si pt a intelege heapurile, pentru cine nu stie deja cu ce se mananca algoritmii de baza ai grafurilor
http://informatrix.ro/informatica/dijkstra.pas.php

[•Marius]

Apropo de STL in C++, am facut un program cu heap-uri care s-a dovedit de aproximativ 10 ori mai rapid decat cel cu priority queue din STL!   
Cine e vinovatul: eu sau STL ?

[•svalentin]

STL este intradevar ceva mai lent.. dar nu cred ca este chiar de 10 ori..

[•domino]

Stiam ca nu poti Dijkstra cu heap-uri cu priority_queue (si sa pastrezi complexitatea M*lg N), eventual cu set.

[•Cosmin]

Poti dijkstra cu heapuri din stl in complexitate O(m log m) cu "lazy deletion", de fiecare data cand ai micsora distanta la un nod si ai modifica in heap, acum adaugi la heap acelasi nod cu un cost mai mic ...

[•domino]

STL e bun in multe momente, dar nu cred ca se merita la Dijkstra.

[•Cosmin]

Nu neaparat, pe topcoder foloseste lumea Dijkstra scris in felul asta destul de mult, e foarte usor de implementat si e O(m log m) in loc de O(N^2). Unde limita de timp nu e foarte stransa se poate folosi usor. Nu stiu cum a implementat Marius, dar totusi nu cred ca o implementare ok folosind STL merge de 10 ori mai incet decat una ce nu foloseste STL.

[•bogdan2412]

Merge cam la fel de repede de fapt...  l-am implementat acum ceva timp cu Set-uri... E scurt si rapid

[•gogu]

E de fapt aceasi complexitate pentru ca O(logM) e echivalent cu O(logN). Doar memorie e mai multa daca inteleg eu algoritmul.

[•Cosmin]

Stiu ca e aceiasi complexitate , singura diferenta fata de algoritmul standard e ca in heap o sa fie cel mult M valori in loc de N valori. Nu stiu ce ziceti voi de set, eu ziceam de priority_queue.

[•svalentin]

A incercat cineva ambele implementari, si cu priority_queue si cu set? E vre-o diferenta de timp? Cu set vine logN, dar cu constanta mai mare..

[•nash]

Dijkstra in O(m log m) cu "lazy deletion" ... nu prea mi-a fost clara ideea .... poate sa detalieze cineva ?

Later Edit: Mi-am dat seama ... ... draguta ideea ori si cum

editat de moderator: nu mai posta de 2 ori consecutiv, mai ales daca este vorba despre aceeasi idee