003 Floyd-Warshall/Roy-Floyd

[•filipb]

Aici puteti discuta despre problema Floyd-Warshall/Roy-Floyd.

[•Mishu91]

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 

[•fireatmyself]

sa se determine pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y

B-C-E-B este un ciclu.

[•Mishu91]

B-C-E-B este un ciclu.

Dap ... n-am citit fff atent 

[•k_ounu_eddy]

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

[•stef2n]

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.

[•k_ounu_eddy]

Sa zicem ca am inteles cam ce vroiam eu .Tx

[•Cosmin]

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

[•stef2n]

Ah, da. Greseala mea

[•wefgef]

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

Mie mi-a luat cativa ani ca sa inteleg exact ce face roy-floyd. M-am multumit sa stiu ordinea k, i, j . 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.

[•k_ounu_eddy]

Deci variabila k reprezinta lungimea drumului

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?

[•wefgef]

Ai putea sa incerci in Cormen.

[•k_ounu_eddy]

ok 

[•Cosmin]

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.

[•alexandru92]

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

[•gabor_oliviu1991]

conditie ar trebui sa fie asa:

Cod:

a[ i ][ k ]!=0&&a[ k ][ j ]!=0&&(a[ i ][ k ]+a[ k ][ j ]<a[ i ][ j ]|| a[ i ][ j ]==0) && i!=j

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

[•alexandru92]

multumesc:D

[•marcelcodrea]

Cred că problema Coach a lui Radu Berinde se foloseste cel mai bine de componenta intrinsecă a algoritmului Roy - Floyd :

Algoritmul calculeaza la pasul k drumurile optime intre i si j care folosesc ca noduri intermediare nodurile din multimea {1, 2, ... k}.

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

[•Bogdan_tmm]

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

[•Mishu91]

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

[•Bogdan_tmm]

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

[•cristiprg]

pot exista costuri negative?

[•philip]

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.

[•cristiprg]

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?

[•philip]

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.