009 Algoritmul lui Dijkstra

[•AlexandruValeanu]

Am si eu o curiozitate daca N < 1000 si M < N*N este mai buna varianta N*N sau cea MlogN ( teoretic cea N*N ) e mai buna pe cazul maxim nu?

[•klamathix]

Da, pe grafuri dense brutul bate M log N-ul. La fel si Prim-ul in N ^ 2 bate ceilalti algoritmi de APM

[•AlexandruValeanu]

Mersi mult de raspuns

[•Flameingo]

spuneti-mi va rog de ce sursa asta http://www.infoarena.ro/job_detail/985164?action=view-source are TLE pe 5 teste? folosesc o coada de prioritate in loc de heap, iar daca inlocuiesc priority_queue-ul cu un queue simplu intra in timp. Multumesc anticipat

[•SebiSebi]

Tu iei TLE deoarece incerci sa relaxezi muchiile incidente unui nod de mai multe ori. Foloseste un vector caracteristic. Iar atunci cand inlocuiesti coada de prioritati cu o coada normala, tu de fapt faci Bellman Ford.

[•CosminRusu]

spuneti-mi va rog de ce sursa asta http://www.infoarena.ro/job_detail/985164?action=view-source are TLE pe 5 teste? folosesc o coada de prioritate in loc de heap, iar daca inlocuiesc priority_queue-ul cu un queue simplu intra in timp. Multumesc anticipat

Pentru ca sa implementezi Dijkstra pe Heap-uri ai nevoie de un Min-Heap !
priority_queue < type > e max-heap. Pentru a implementa Min-Heapul folosind STL faci asa:

Cod:

priority_queue <nod, vector<nod> , greater<nod> > MINHEAP;

Sau iti poti face propria ta clasa de comparare, ca aici: http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

Pentru mai multe informatii consulta asta : http://www.cplusplus.com/reference/queue/priority_queue/ .

Spor!

[•Cosmin1490]

Sursa http://www.infoarena.ro/job_detail/989978 cu Set de la indicatii ce ar trebui sa obtina 80 de puncte acum scoate 90-100 la limita.
Si de mentionat ca o imbunatatire ar fi eliminarea intrarii din set si inserarea unei intrari noi atunci cand actualizam distanta unui nod.

Noii timpi obtinuti : http://www.infoarena.ro/job_detail/989976

[•AlexandruValeanu]

Asta pentru ca poate a fost imbunatatit compilatorul...

[•AlexandruValeanu]

Am si eu o nelamurire: Dijkstra cu costuri mici implementat ca in articolul din GInfo ia 70p cu 3 TLE. Daca scot functia de stergere din vechea lista ( ceea ce teoretic este o greseala ) ia 100p. Asa ar trebui sa se intample sau nu sunt propuse testele astfel incat astfel de solutii sa nu ia 100?

[•Sapientia]

Killed by signal 11(SIGSEGV)-Ce semnifica mesajul ?

[•rares96cheseli]

Killed by signal 11(SIGSEGV)-Ce semnifica mesajul ?

Citeste aici http://www.infoarena.ro/documentatie/evaluator la Mesaje de evaluare

[•jumper007]

Hm.. Dacă vă rog, îmi poate spune și mie cineva de ce nu e bun codul meu? Iau doar 10 pct.. Ideea algoritmului am luat-o de pe TopCoder dintr-un tutorial. Era un Dijkstra rezolvat pe baza unui priority_queue<T, vector<T> >. Pe toate testele pe care i le-am dat, rulează ok, nu înțeleg de unde provine problema.

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

EDIT: TopCoder ref http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#dijkstra2

Mulțumesc anticipat.

[•mirceadino]

Citeste cu atentie restrictiile problemei

[•jumper007]

Restrictii
1 ≤ N ≤ 50 000
1 ≤ M ≤ 250 000
Lungimile arcelor sunt numere naturale cel mult egale cu 1 000.
Pot exista arce de lungime 0
Nu exista un arc de la un nod la acelasi nod.
Daca nu exista drum de la nodul 1 la un nod i, se considera ca lungimea minima este 0.
Arcele date in fisierul de intrare nu se repeta.

Deci, eu afisam INT_MAX pentru drumurile care nu exista, acum afisez 0 in schimb, dar tot nu primesc punctele

[•PlayLikeNeverB4]

Nu ar trebui sa extragi intai nodurile cu distanta cea mai mica?

[•jumper007]

Ah scuze, țin minte că scrisesem acea parte, dar cred că am șters-o ieri din greseală.. Mersi

[•johny]

Vă rog dacă poate să verifice cineva sursa:
http://www.infoarena.ro/job_detail/1172258?action=view-source

Timpii de rulare sunt foarte buni, dar la memoria folosită apare doar
memorie depăşită: http://www.infoarena.ro/job_detail/1172258

Cum pot afla care este dimensiunea memoriei folosite?

[•AlexandruValeanu]

Timpii de rulare sunt buni pentru ca programul nu este rulat pana la sfarsit, deoarece iese din memorie destul de repede din cauta reprezentarii grafului folosind cozi. Daca muti programul pe vector: http://www.infoarena.ro/job_detail/1172397?action=view-source o sa-ti intre in memorie. Pentru obiectele din STL nu poti calcula prea usor cata memorie consuma, de aceea e bine sa le eviti. Oricum citeste asta daca te intereseaza: http://stackoverflow.com/questions/7448514/how-can-i-know-how-much-memory-an-stl-object-takes si http://stackoverflow.com/questions/14784551/c-stl-queue-memory-usage-compared-to-vector

[•johny]

Multumesc pentru ajutor, Alexandru!
Am gasit de unde era eroarea:
obiectele queue sunt alocate ineficient.

[•witsel]

scz ca intreb, dar ce inseamna INF=1 << 30;??

[•visanr]

1 << 30 = 2³⁰
Ai aici un articol unde sunt explicate operatiile pe biti

[•depevlad]

Am facut pentru problema asta 2 surse, una in care am folosit algoritmul lui Dijkstra "ca la carte", si una in care faceam un fel de bfs - bagam un element in coada, ma duceam la toti vecinii, iar daca distanta noua pana la vecini este mai mica decat distanta veche, reintroduceam vecinul in coada si recalculam. A doua sursa a luat, neasteptat, tot 100 pct. Ba chiar a obtinut timpi mai buni de executie, in medie, decat abordarea clasica cu Dijkstra. Cum e posibil acest lucru, nu ar trebui sa aiba o complexitate mai mare, care trage spre n patrat?  As aprecia mult daca m-ar ajuta cineva sa inteleg cum sursa aparent mai proasta o depaseste pe cea cu Dijkstra.

Iata cele doua surse si borderourile de evaluare:

1. Dijkstra:
http://www.infoarena.ro/job_detail/1399323 - borderou
http://www.infoarena.ro/job_detail/1399323?action=view-source - sursa

2. BFS:
http://www.infoarena.ro/job_detail/1399062 - borderou
http://www.infoarena.ro/job_detail/1399062?action=view-source - sursa.

Multumesc anticipat 

[•alex_bucevschi]

Ceea ce faci tu in a doua sursa e Bellman-Ford care are cam aceeasi complexitate cu Dijkstra http://www.infoarena.ro/problema/bellmanford

[•Sagunistu]

Dijkstra are complexitate O(M*logN), iar Bellman-Ford are O(M*N). Bellman Ford cu coada, asa cum l-ai facut tu, are aceeasi complexitate O(M*N), dar in practica e la fel de bun ca Dijkstra. Practic, niciodata nu o sa faca N*M pasi. Bellman-Ford e util cand ai costuri negative pe muchii, deoarece atunci Dijkstra nu merge.

[•mouse_wireless]

In "indicatiile" problemei scrie ca o rezolvare cu set va lua doar 80 de puncte dar eu am trimis cu set si am luat 100  .. si nu m-am chinuit prea mult cu optimizari. Poate ar trebui redusa un pic limita de timp?