003 Floyd-Warshall/Roy-Floyd

[•xdoze]

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.

[•skull]

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

[•alexandru92]

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 ]

[•Bogdan_tmm]

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

[•xdoze]

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?

[•popoiu.george]

Sa presupunem ca nu cunosc notiunea de graf si vreau sa aflu costul minim dintre doua celelule ale unei matrici

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

[•APOCALYPTO]

Jumatate din teste contin grafuri complete?

[•Bit_Master]

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?

[•Magnus]

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

[•Bit_Master]

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

ms

[•pauldb]

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.

[•edihackpack]

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

[•gabitzish1]

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

[•radustn92]

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?