== include(page="template/taskheader" task_id="dijkstra") ==

Se da un graf orientat si ponderat cu $N$ noduri si $M$ arce.

Se da un graf orientat cu $N$ noduri si $M$ arce.

h2. Cerinta

h3. Indicatii de rezolvare

Exista o descriere a algoritmului pe "wikipedia":http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Exista o descriere a algoritmului pe 'wikipedia':http://en.wikipedia.org/wiki/Dijkstra's_algorithm.

O rezolvare de complexitate {$O(N^2^)$} obtine $40$ de puncte si se poate gasi 'aici':http://infoarena.ro/job_detail/144256?action=view-source.
O rezolvare in {$O(Mlog{~2~}N)$} folosind un heap obtine $100$ de puncte si se poate gasi 'aici':http://infoarena.ro/job_detail/144254?action=view-source. O descriere a acestei structuri de date puteti gasi tot pe 'wikipedia':http://en.wikipedia.org/wiki/Binary_heap *Feedback(Silviu)*: Vom finaliza 'articolul':heapuri despre heapuri in curand. De asemenea Dijkstra se poate implementa si cu Arbori de intervale sau set-uri STL. Sper sa avem in viitorul apropiat un articol despre Dijkstra in care sa fie explicate abordarile astea :)

O rezolvare de complexitate {$O(N^2^)$} obtine $40$ de puncte si se poate gasi 'aici':job_detail/144256?action=view-source.
O rezolvare in {$O(Mlog{~2~}N)$} folosind un heap obtine $100$ de puncte si se poate gasi 'aici':job_detail/144254?action=view-source. O descriere a acestei structuri de date puteti gasi tot pe 'wikipedia':http://en.wikipedia.org/wiki/Binary_heap. O implementare de aceeasi complexitate foloseste in loc de heap structura de date numita SET, care este de fapt un arbore binar echilibrat si permite interogarea costului minim si modificarea costurilor in timp logaritmic. Aceasta abordare se gaseste 'aici':job_detail/144699?action=view-source si are avantajul ca necesita un cod mult mai scurt. Totusi, ea este mai inceata decat solutia cu heap-uri.

h3. Probleme asemanatoare