Witam mam grafy tego typu:
Gdzie kolejne wierzcholki (vi) grafu zaznaczone sa w kolach. Wartosci na laczeniach (a|b) to kolejno a - koszt przebycia z v0 do v1
oraz b - okres co jaki czas mozemy dostac sie do kolejnego wierzcholka. Moim zadaniem jest znalezc najkrotsza sciezke dla tego typu grafow. Probowalem szukac wszystkich mozliwych sciezek dla przebcia od 0 do 3, a nastepnie dla kazdej sciezki liczyc wlasciwie okres, ktory musi byc uaktualniany przy kazdym wyborze jednak takie rozwiazanie jest zbyt wolne.
Przyklad: start 0 stop 3
Mozliwe sciezki: a) 0->1->2->3 oraz b) 0->1->3
a)
I. 1 + 1(czekamy dodatkowo minute) = 2 (minely 2 minuty)
II. 2(czas ktory juz minal) + 2 + (2 - 2) = 4 (odejmujemy 2 bo okres jest dla calej trasy czyli teraz jestesmy akurat na czas)
III. 4 + 3 + (3 - 4 +[3]) (mamy liczbe ujemna czyli minal jeden okres dodajemy +3, czekamy jeszcze 2 minuty)= 9 (koniec podrozy)
b)
I. 1 + 1 = 2
II. 2 + 1 + 8 (czekamy jeszcze 8minut) = 11 (koniec podrozy)
Tyle udalo mi sie wywnioskowac. Probuje zaimplementowac teraz dijkstre i jakos ja zmodyfikowac zeby dobrze znalezc najkrotsza sciezke tak by uwzlegniac prawidlowo ten okres jednak nie moge rozgryzc. Jest moze jakis prostszy sposob? Ktos sie spotkal z takim problemem?