Myslenka, kterou zde uvadim je nasledujici: vytvorit novy graph, ktery bude obsahovat pouze pumpy (vcetne Start a cil, protoze maji take pumpy) a potom v novem grafu najit nejlepsi cestu pomoci Dijkstry aniz bychom resili benzim. To lze udelat v 3 nasledujicich krocich:
Pocitam (pomoci Dijkstry ) nejlepsi cestu mezi Startem a mesty s pumpou (vcetne cilu, je-li to mozne). Budu zde ale brat ohled na benzin. Muze se tedy stat, ze mi na ceste dojde a nebudu moci pokracovat dale. Pokud jsem tedy schopen dojit ze Startu do nejakeho mesta M s pumpou ve vzdalenosti D, pak vytvorim v novem grafu hranu (start, M) = D; Uzel M se tedy stane sousedem Startu v novem grafu.
Spustim opet Dijsktru tento krat z kazdeho mesta s pumpou do jinych mest s pumpou (vcetne cilu), kam jsem schopen dojet(opet zalezi na benzinu). Pak zase vytvorim v novem grafu hrany mezi mestem s pumpou odkud jsem zacal a kazdem mestem s pumpou, kam jsem dojel.
Pomoci techto dvou kroku dostanu tedy novy graf, ktery bude obsahovat pouze start, vsechna mesta s pompou, kam jsem byl schopen dojet a cil. Hrany jsou pak nejlepsi cesty, ktere mi vratil Dijkstra. Protoze v tom novem grafu jsou same pumpy, uz neni potreba pocitat benzin. Spustim tedy klasicky algoritmus Dijkstry v tom novem grafu a vysledek je reseni.
V 1. a 2. kroku se muze stat, ze spocitam nejakou hranu 2 nebo vic krat. Je tedy potreba nejdriv kontrolovat jestli jsem nejakou hranu nepocital, predtim nez ji budu pocicat.