Bellman-Ford

[•stef2n]

Unde gasesc si eu algoritmul lui Bellman-Ford explicat si eventual implementat? Ca in manualele actuale nu este nici macar amintit... Multumesc anticipat!

[•danielp]

Incearca sa cauti in cartea "Introducere in algoritmi". E publicata la editura Agora, dar casesti si versiunea in engleza pe net. Linkul il poti gasi la http://info.devnet.ro la sectiunea resurse web cred...

[cristi8]

http://www.google.com/search?q=bellman+ford

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

[•stef2n]

Multumesc mult! Mi-au fost de ajutor link-urile voaste... Inca o intrebare: pentru grafuri cu arce negative merge si Floyd-Warshall, nu-i asa?

[•vladcyb1]

Floyd-Warshall merge si pe arce negative dar am impresia ca nu e voie sa exise cicluri negative...daca am zis o prostie atunci  

[•svalentin]

daca ar exista cicluri negative, atunci drumul de la orice nod la orice nod va trece intai prin ciclul ala ca sa scoata costul drumuui -oo ... (de fapt, orice nod care are legatura cu ciclur respectiv)

[•pauldb]

Cum pot aplica Bellman Ford intr-un graf orientat asa incat sa-mi dau seama daca exista cicluri negative oriunde in graf?
[nu este neaparat ca ciclul sa contina nodul sursa]

[•svalentin]

hmm.. pai, faci un DF dintr-un nod si vezi pe unde ajunge parcurgerea in graf.. apoi faci Belllman_Ford din acelasi nod, verifici daca are cicluri, apoi iei alt nod in care nu ai ajuns cu primul DF si il consideri radacina..
nu stiu cat de bine merge/ daca merge, e prima idee care o am, sper ca te ajuta... poate poti sa o rafinezi

[•azotlichid]

vezi Cormen 
Daca graful nu contine cicluri negative, dupa ce au fost relaxate toate muchiile de maxim V - 1 ori, nici una dintre ele nu va mai putea fi relaxata. In caz contrar..are ciclu negativ.