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?
Hovorí ti niečo backtracking? Skús to tak. Mňa to naučil život a potom som sa dozvedel, že je to bežné učivo na VŠ. Jedná sa o to, že pôjdeš z jedného miesta, tam si zistíš všetky časy na všetky smery. Uložíš to všetko do poľa a pokračuješ v koncových polohách. Presnejšie povedané, nie pokračuješ, ale opakuješ presne ten istý postup dokým nenájdeš riešenie. Samozrejme cestu od začiatku si musíš niekde ukladať. Ak sa dostaneš na miesto, kde si už bol, tak to preskočíš. Ak nájdeš riešenie (dostaneš sa do cieľa), tak nechaj nejakú toleranciu, pretože sa môže nájsť cesta s viacerými zastávkami, ale kratšia. Ak budeš mať toleranciu prekročenú o n zastávok, vyhodnoť najkratšiu cestu zo všetkých riešení a máš výsledok.
Edit: Môžeš to dokonca zrýchliť tak, že ak nájdeš riešenie, tak všetky cesty, ktoré majú dlhší čas ako nájdené riešenie mažeš za jazdy zo zoznamu. Nakoniec dojdeš k jedinému riešeniu a cesta už nebude existovať. Vtedy máš zaručene najkratšiu cestu a nepotrebuješ dokonca ani toleranciu.
tohle je brutálně neefektivní a navíc hrozí zacyklení..¨
nejdeš na to blbě, ale vymýšlíš znova kolo: Teorie_graf%C5%AF
Ne vejšce do nás tlačili cosi pod názvem Borůvkův hladový algoritmus. Jistě to půjde najít přes gůgl. Jestli se dá napasovat na tvůj problém, to opravdu netuším.
Pavel
Áno, Dijkstrov algoritmus funguje aj na orientovanom grafe.
Na vysokej skole sme sa ucili Floydov algoritmus na najdenie takejto cesty... musel by som niekde vyhrabat svoje poznamky ako to funguje... treba to len vygooglit...
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