najkratšia cesta v grafe
Dobrý deň,
chcem spraviť aplikáciu na vyhľadávanie najkratšej cesty v ohodnotenom grafe. Pôjde o turistické chodníky a za najkratšiu cestu sa bude považovať najrýchlejšia trasa. Teda hrany grafu budú ohodnotené časmi v minútach. Problém je v tom, že neviem aký algoritmus bude najvhodnejší.
Dijkstrov algoritmus je vhodný na graf kde cesta z A do B je taká istá ako z B do A (AB=BA), to ale neplatí pri turistických chodníkoch, kde je čas rozdielny podľa toho či idete hore kopcom, alebo dole kopcom, takže z A do B môžem ísť dlhšie ako z B do A.
Dal by sa použiť ten Dijkstrov, keby som opačný smer pridal ako ďalšiu hranu v grafe? Alebo existuje nejaký iný vhodnejší spôsob/algoritmus?
Ten Floyd-Warshallov algoritmus je presne to čo potrebujem - nájsť najkratšiu cestu v ohodnotenom, orientovanom grafe.
Ďakujem všetkým za správne nasmerovanie. Možno niekomu pomôže odkaz na popis toho Floydovho algoritmu, je to aj s odkazmi na ukážky použitia http://en.wikipedia.org/wiki/Floyd-Warshall_algorit hm