009 Algoritmul lui Dijkstra

[•Florian]

Parseaza citirea. Si eventual foloseste un viz[] ca aici.Succes!

[•Pepelea_Flaviu]

Are si el vectorul viz in program cu aceasi semnificatie. Insa, el adauga tot la sfarsit noduri, iar astfel exista riscul de a ii iesi din limitele cozii. Alternative ar fi: sa adaugi intodeauna un nod pe pozitia (poz_ult_nod_din_lista + 1) % N, unde N este numarul de noduri, sa incerci sa folosesti coada din stl sau sa implementezi o coada dinamica.

[•c_e_manu]

am implementat o coada dinamica, am probleme doar cu timpul la ultimul test... am incercat si varianta lui Florian, mai putin parsarea citirii... deci probabil de acolo se trage TLE-ul... am incercat si citire in C si streamuri... acelasi rezultat... acum e prea tarziu sa mai incerc coada din STL, poate maine... multumesc oricum de raspunsuri!

[•razyelx]

Imi poate explica si mie cineva de ce Dijkstra nu merge pe costuri negative, va rog. Eu l-am implementat si am pus doua muchii negative si mi-a mers de minune. Deci cum e cu asta?

[•wefgef]

Se da urmatorul graf orientat:

Cod:

4 4
1 2 5
1 3 10
3 2 -7
2 4 5

Iti da bine?

[•alexthero]

Pe scurt, muchiile negative nu merg cu Dijkstra deoarece in momentul in care scoti un nod din heap (nodul cu cel mai mic cost) tu il consideri terminat (cost optim in el). Sa-ti dau un exemplu. Sa presupunem ca ai muchia de la 2 la 1 cu costul -5. In Dijkstra ai ajuns sa ai d[1] = 4 si d[2] = 5. Nodul cu cel mai mic cost e 1, deci il scoti din heap si ai terminat socoteala cu el. Insa exista un cost mai bun pe care nu l-ai luat in calcul, si anume drumul care ajunge in nodul 2 cu costul 5, si apoi ia muchia de la 2 la 1, ajungand in 1 cu costul 0.

[•razyelx]

Ms fain. Acum am inteles si eu care e treaba. Daca exista costuri negative, atunci se poate intampla ca drumul de la un nod i la un nod j sa scada(prin adunare cu o valoare negativa), iar daca nodul j a fost selectat in trecut atunci drumurile care au trecut de la i prin j, nu vor fi actualizate cu noua valoare. Mda.. inca o data ms fain. 

[•philip]

Cum de reuseste sursa http://infoarena.ro/job_detail/256683?action=view-source sa ia 100 de puncte?
E doar dijkstra simplu, fara heap. Care e complexitatea finala?

[•CezarMocan]

Ala nu e Dijkstra, e Bellman-Ford (cred )

[•philip]

Ala nu e Dijkstra, e Bellman-Ford (cred )

Si coada unde e?

[•bogdan2412]

Bellman Ford original nu e cu coada: Se parcurg toate muchiile i, j si se updateaza de fiecare data costul nodului j daca costul nodului i + costul muchiei e mai mic decat costul curent al nodului j si se repeta asta de N-1 ori. Coada e doar o optimizare.

[•philip]

Bellman Ford original nu e cu coada: Se parcurg toate muchiile i, j si se updateaza de fiecare data costul nodului j daca costul nodului i + costul muchiei e mai mic decat costul curent al nodului j si se repeta asta de N-1 ori. Coada e doar o optimizare.

Stiu ca e doar o optimizare. Intrebarea mea era cum reuseste sa ia 100 de puncte, neoptimizat.

[•toni2007]

Sunt testele proaste daca nu ma insel, programul se bazeaza pe faptul ca nu o sa faca mai mult de logN operatii repeat. Fiecare repeat are complexitatea o(m). Daca dau un test de forma:

Cod:

10 11
3 2 1
4 3 1
5 4 1
6 5 1
7 6 1
8 7 1
9 8 1
10 9 1
11 10 1
1 11 1
1 2 10000000

Va face N operatii repeat.

[•philip]

OK, am inteles. Mersi!

[•cristiprg]

ciudat, am rezolvat-o de 40 puncte (cel putin asa cred) dar imi da TLE pe testele 2, 3, 4, care in mod normal nu are de ce. daca dau copy, paste in fisieru de intrare la mine pe calculator, merge fara probleme ...  nu ar trebui sa se comporte la fel?

[•cotofana]

imi poate spune si mie cineva dc cu sursa asta am luat 100?
http://infoarena.ro/job_detail/280886
daca va uitati la functia percolate variabila father ramane una si aceeasi, nu se modifica in interiorul whilelului
is testele chiar in halu ala de slabe ?, ca la alte probleme unde trebea heap ma uitam la sursa asta sami amintesc functiile sift si percolate si luam doar 10-20 de pct tocmai din cauza acestei greseli
(sau is io batut in cap si numi inteleg propriul cod )

[•Mishu91]

Am și eu o nelămurire. Cu sursa asta obțin 100 de puncte, însă dacă renunț să mai marchez un nod ales cu distanța cea mai mică până în acel moment ca fiind neintrodus în heap, iau 60. Deci un nod mai poate fi introdus în heap după l-am vizitat odată? Destul de ciudat, având în vedere că la fiecare pas extrag nodul cu distanța minimă.

[•blasterz]

Am și eu o nelămurire. Cu sursa asta obțin 100 de puncte, însă dacă renunț să mai marchez un nod ales cu distanța cea mai mică până în acel moment ca fiind neintrodus în heap, iau 60. Deci un nod mai poate fi introdus în heap după l-am vizitat odată? Destul de ciudat, având în vedere că la fiecare pas extrag nodul cu distanța minimă.

Tu faci Lazy Dijkstra ...

Tu updatezi doar daca nu mai ai nodul in PriorityQueue... ceea ce nu e bine
(adica heapul nu se reface... dar distanta da)

[•Mishu91]

Adică Lazy Dijkstra nu mai garanteaza O(M logN)?

[•blasterz]

ba garanteaza (cred ca e MlogM ... nu sunt sigur)

[•mimarcel]

M-am uitat peste unele surse si am observat ca se declara vectorul cu muchii de 250002 elemente, insa maximul de muchii este 250000. Este necesar acest lucru sau la ce ajuta? Eu am rezolvat problema folosind un vector cu 250000 de pozitii.

Am inteles. Mersi pentru raspunsuri!

[•gabitzish1]

Unii declara tablourile cu 2-3 elemente in plus, pentru siguranta. Se poate intampla sa declari fix, si sa depasesti spatiul declarat daca nu esti atent si nu indexezi de la 0, sau cine stie din ce alte motive.

[•alexandru92]

M-am uitat peste unele surse si am observat ca se declara vectorul cu muchii de 250002 elemente, insa maximul de muchii este 250000. Este necesar acest lucru sau la ce ajuta? Eu am rezolvat problema folosind un vector cu 250000 de pozitii.

Nu este bine sa declari un vector exact de cat ai nevoie, poate sa crape programul. Daca este lucat in considerarea faptul ca vectorul este indexat de la 0 la n-1 atunci e ok, dar da incepi de la 1 o sa ai surprize .

  

[•Prostu]

M-am uitat peste unele surse si am observat ca se declara vectorul cu muchii de 250002 elemente, insa maximul de muchii este 250000. Este necesar acest lucru sau la ce ajuta? Eu am rezolvat problema folosind un vector cu 250000 de pozitii.

Nu este bine sa declari un vector exact de cat ai nevoie, poate sa crapa programul. Daca este lucat in considerarea faptul ca vectorul este indexat de la 0 la n-1 atunci e ok, dar da incepi de la 1 o sa ai surprize .

In general cred ca este bine sa declari vectorul exact atat cat iti trebuie, dar in cazul rezolvarii problemelor pentru olimpiada o neatentie te poate costa scump, asa ca multi prefera sa fie de partea sigura a baricadei si declara vectorii mai mari pentru ca se intampla de multe ori sa accesezi ceva care este la pozitia n+1 sau n+2.

[•popoiu.george]

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 !