infoarena

Aici puteti discuta despre problema Floyd-Warshall/Roy-Floyd (http://infoarena.ro/problema/royfloyd).

Dar de ce se considera ca nu exista drum intre un nod si el insusi, pentru ca daca de exemplu exista drum intre B si C , intre C si E si intre E si B, atunci exista drum de la B la B: B-C-E-B  :)

B-C-E-B este un ciclu.

Dap ... n-am citit fff atent  ](*,)

Nu am inteles prea bine faza aia cu ordinea lui k,i si j.De ce trebuie sa fie neaparat asa?Intuiesc eu de ce,dar nu pot sa demonstrez.Este din cauza ca dak nu avem forurile in ordinea k,i,j, drumurile nu o sa mai fie optime,nu?De ce?
Am cautat pe mai multe site-uri si nu am gasit raspunsul

Roy-Floyd e un algoritm de programare dinamica. Mai intai calculeaza pentru drumurile de lungime 1 intre oricare 2 noduri i si j, apoi pentru drumurile de lungime 2, etc. Deci variabila k reprezinta lungimea drumului. Incearca sa retii ideea din spatele algoritmului, si nu doar ca sunt 3 for-uri in ordinea k, i, j.

Sa zicem ca am inteles cam ce vroiam eu .Tx

Stefane nu e bine ce ai zis. Algoritmul calculeaza la pasul k drumurile optime intre i si j care folosesc ca noduri intermediare nodurile din multimea {1, 2, ... k}.

Incearca sa retii ideea din spatele algoritmului, si nu doar ca sunt 3 for-uri in ordinea k, i, j :P

Ah, da. Greseala mea :oops:

Mie mi-a luat cativa ani ca sa inteleg exact ce face roy-floyd. M-am multumit sa stiu ordinea k, i, j :P. Acelasi lucru l-am facut si la arbori indexati binar, kmp si la flux. Nu e ok sa inveti pe de rost un algoritm, desi in concurs te poate ajuta sa implementezi corect o solutie de care te prinzi. Daca nu intelegeti ceva, e bine sa reveniti asupra lui periodic, inarmati cu noi cunostinte, pana cand sunteti convinsi ca e totul limpede.

Cred ca ce vroia sa spuna Stefan,e ca la fiecare pas,intre i si j se afla maxim k noduri intermediare.

@wefgef:Stii vreun articol,vreun site in care sa se explice mai bine cum functioneaza Roy-Floyd?

Ai putea sa incerci in Cormen.

ok  :)

Nu k noduri intermediare, ci noduri intermediare din multimea {1, 2, .. k}. Daca nu ai Cormenul la indemana poti sa cauti pe google de exemplu wikipedia are o explicatie a algoritmului.

Imi spune si mie cineva unde gresesc  la sursa sa deja turbez  ](*,)
http://infoarena.ro/job_detail/277712?action=view-source

conditie ar trebui sa fie asa:


cred ca uiti "sau"-ul ala. actualizezi a[ i ][ j ] ai daca drumul de la i->j ii mai mare decat i->k->j sau nu ai drum deloc

multumesc:D

Cred că problema Coach  (http://infoarena.ro/problema/coach) a lui Radu Berinde se foloseste cel mai bine de componenta intrinsecă a algoritmului Roy - Floyd :


Propun să fie introdus un link catre Coach, acolo unde se propune ca exerciţiu explicarea ordinii iteratorilor.

Dar daca am aplica dijkstra pentru fiecare  nod? Nu ar fi corect?

Ba da, este același lucru. Dar există probleme unde se folosesc proprietățile algoritmului Roy-Floyd (vezi Coach).

Dar complexitatea in loc de n^3 devine n*m* log n
L.E. Pentru numar mare de muchii nu are rost:)

pot exista costuri negative?

La problema asta nu o sa fie, insa algoritmul Floyd-Warshall/Roy-Floyd merge si pe grafuri cu costuri negative.
Ciclurile sunt cele care trebuie sa fie tot timpul pozitive.

dar algoritmul determina cicluri de cost negativ? nu prea vad cum ... pentru ca is alea 3 for-uri,  si atat, eventual numa daca mai aplici inca o data Roy-Floyd, si tot mai poti imbunatati costuri....atunci exista ciclu negativ?

Poti afla daca ai cicluri negative dupa prima aplicare Roy-Floyd asa... verifici diagonala principala din matricea costurilor (drum minim de la i la i) si daca ai cost negativ inseamna ca ai un ciclu de cost negativ.
Dar nu cred ca ar trebui sa apara la vreo problema cicluri de cost negativ. Nu prea are sens.

Salut.Am inceput sa scriu cod de foarte putin timp.Particip la OJI 2010 la liceu si am invatat roy-floydul dintr-un manual. Imi ies testele corect(matricea se construieste bine) dar nu stiu sa o interpretez.As vrea daca se poate sa ma lamureasca cineva cum pot sa aflu drumul minim conform matrici rezultate.(presupunand ca asta ar trebui sa faca roy-floydul).Multumesc.

Valoarea din a[ i][j] reprezinta costul minim de la nodul i la nodul j. Incearca totusi sa intelegi cum functioneaza algoritmul.

Folosind Roy-Floy determini costul drumului minim intre oricare 2 noduri din graf.  La fiecare pas el compara distanta intre i->j si i->k->j ( interpune un nod k ca sa vada daca  distanta ar fi mai mica ). Astfel drumul minim de la i->j va fi in matricea a[ i ][ j ] :)

Ai aici un exemplu despre cum descompui drumul
http://infoscience.3x.ro/c++/roy_floyd.htm (http://infoscience.3x.ro/c++/roy_floyd.htm)

Sa presupunem ca nu cunosc notiunea de graf si vreau sa aflu costul minim dintre doua celelule ale unei matrici, cum imi dau seama care este drumul minim conform matricii rezultate?

Poti sa faci o dinamica cu o coada. Daca vrei detalii PM me.

Jumatate din teste contin grafuri complete?

ideea la algoritmul acesta e ca e rapid de implementat decat dijkstra, nu?

ca de n ori dijkstra cu heap-uri ar avea complexitate O(N^2 * logM) in loc de O(N^3)...

sau mai are si alte avantaje?

ideea la algoritmu' asta este ca merge pe grafuri cu costuri negative, spre deosebire de dijkstra :eyebrow:

ms

De asemenea e mai avantajos atunci cand M este aproximativ N². Pentru aceste cazuri daca ai face de N ori Dijkstra cu heap ai obtine complexitatea O(N³logN). Facand de N ori Dijkstra clasic, complexitatea e O(N³), dar constanta e putin mai mare.

Zice ca n e maxim 100, si n-ul din primul test e 200.

M'am uitat prin atasamente ... si nu e niciun test cu N 200 ..

Am incercat sa rezolv pb asta folosind Java https://infoarena.ro/job_detail/2224736 . Cele 2 TLEs par sa fie din cauza citirii din Java (citirea este facuta eficient folosind un buffered reader) . Se poate mari limita de timp pt sursele in Java?