047 Algoritmul Bellman-Ford

[•mihaipopa12]

Pai vezi ca in cazul vectorului din STL nu simulezi coada, scoti de la sfarsit iar tu ar trebui sa scoti de la inceput.

[•danalex97]

Acum mi-am dat seama si vroiam sa sterg postarea.   Multumesc oricum.

[•klamathix]

Vectorul ala nu simuleaza o coada. Principul cozii este ca primul venit e primul plecat. Iar tu ai Q.pop_back() respectiv Q.push_back() in sursa ta. La tine urmatoarea chestie pe care o extragi din Q e ultima pe care ai pus-o, ceea ce nu e ok deloc. Asta e o stiva. Coada din STL face pop() din fata, nu din spate  

Acum ca sa vezi de ce merge prost Bellman-ul cu o stivă, e ceva mai complicat. Intuitiv, expandarea ta prin graf se face ca un df, adica ajungi foarte departe din prima cu niste drumuri proaste, te intorci si le imbunatatesti mai apoi, desi puteai face asta de la inceput daca te expandai uniform. O da intr-un fel de back. Sper ca ai inteles. Ai grija sa 'ai proprietatea termenilor pe care ii folosesti', ca sa citez dintr-un ganditor autohton  . Nu scrie chestii pe care nu le intelegi pe deplin si daca ai intrebari, intreaba intotdeauna 

[•danalex97]

Multumesc. Problema a fost doar una de neatentie.    Scuze pentru deranj.

[•andreiulian]

Eu nu inteleg de ce dijkstra nu e bun pentru grafuri cu muchii negative. Imi poate spune cineva?

[•MKLOL]

Eu nu inteleg de ce dijkstra nu e bun pentru grafuri cu muchii negative. Imi poate spune cineva?

Uita-te la acest graf. Care e distanta minima intre A -> C ? Cat gaseste Dijkstra ?

[•sunt_emo]

Poate nu am inteles bine cerinta, dar solutia oficiala pica urmatorul test, desi graful contine in mod clar un ciclu negativ:

4 4
2 1 1
2 3 1
3 4 1
4 2 -3

[•PlayLikeNeverB4]

Solutiile oficiale presupun ca poti ajunge din nodul 1 in orice alt nod. Poate la asta se refera "graf orientat conex", nu imi dau seama.

[•sunt_emo]

Cred ca ai dreptate, desi notiunea de "graf conex" se refera la grafuri neorientate. Pentru grafuri orientate am vazut ca se folosesc notiunile de "tare conex" (testele la problema la asta) si "slab conex" (exemplul pe care l-am dat eu).

[•AndreiGrigoras]

Stiti cumva ce este la testul 6 ? Tot incerc sa inteleg de ce iau doar 90 pct

[•vladrochian]

Stiti cumva ce este la testul 6 ? Tot incerc sa inteleg de ce iau doar 90 pct

Testele sunt publice