infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Bellman-Ford
Pagini: [1]   În jos
« mesajul precedent următorul mesaj »
  Imprimă  
Ajutor Subiect: Bellman-Ford  (Citit de 1284 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•Andreid91
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 54



Vezi Profilul
« : Martie 04, 2010, 21:13:27 »
Salut !

Daca implementez bellman-ford cu coada... cum pot sa evit cazu in care sunt cicluri de cost negativ??

Singura idee : sa retin intr-un vector de cate ori a fost relaxat drumul printr-un nod...si cand o astfel de valoare depaseste n inseamna ca am un ciclu de cost negativ.

In final ,algoritmu ar iesi mai eficient daca l-as implementa fara coada...   Think
Memorat
•alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #1 : Martie 04, 2010, 21:32:31 »
Exista o problema in Arhiva educationala pe aceasta tema + forum specific.
http://infoarena.ro/problema/bellmanford
Daca un nod este introdus de mai mult de n ori in coada inseamna ca ai gasit un ciclu negativ. Implementat cu coada BellmanFord are teoretic complexitatea O( N*M ) dar este mult mai rapid in practica Smile
Memorat
•Andreid91
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 54



Vezi Profilul
« Răspunde #2 : Martie 04, 2010, 21:52:09 »
Daca ma gandesc mai bine... da,  ai dreptate  Very Happy
Memorat
Pagini: [1]   În sus
  Imprimă  
infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Bellman-Ford
 « mesajul precedent următorul mesaj »
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines