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?