|
Titlul: Bellman-Ford Scris de: Ciocan Andrei din 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... :-k Titlul: Răspuns: Bellman-Ford Scris de: alexandru din 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 :) Titlul: Răspuns: Bellman-Ford Scris de: Ciocan Andrei din Martie 04, 2010, 21:52:09 Daca ma gandesc mai bine... da, ai dreptate :D
|