W dniu 2010-07-06 07:40, Maciej Pilichowski pisze:
> On Mon, 05 Jul 2010 08:34:16 +0200, Wit Jakuczun
> <w...@g...com> wrote:
>
>>> Pamietajmy, ze tutaj koszt (czas) jest zalezny od momentu dotarcia,
>>> trzeba sie chwile zastanowic, czy nadal Dijkstry bedzie dobry
>>> (na oko tak).
>>>
>> Obawiam się, że nie będzie.
>
> Czemu? Wezlami nie sa przystanki, ale pociagi (czy autobusy,
> whatever).
>
Temu, że OP nie podał dokładnego sformułowania. Napisał jedynie, że
szuka trasy ale kryteriów nie podał (najkrótsza, najszybsza, dowolna?).
Przykład: http://www.math.tau.ac.il/~hassin/restrictedPath.pdf
Artykuł opisuje problem gdzie szukamy najkrótszej (najtańszej) trasy z
ograniczeniem na czas trwania. Problem jest NP-zupełny. W artykule
podane są pseudowielomianowe algorytmy aproksymacyjne

Twoja sugestia, żeby spojrzeć na problem jako sieć połączeń między
autobusami wydaje się być ciekawa. Z tym, że może zadziałać jedynie
dlatego, że godziny wyjazdu i przyjazdu są ściśle określone (Dzięki temu
dałoby się skonstruować graf powiązań między autobusami z góry (nie
zależny od rozwiązania)). No i trzeba by założyć, że nie jest to problem
z przykładu powyżej.
Dopuszczając możliwość przyjechania w przedziale czasowym (np. rozkład
+/- 15min) problem staje się NP-Complete.

Swoją tu jest przykładowy kod:
http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/
r_c_shortest_paths.html
ze wskazaniem na literaturą. Kodu nie testowałem więc nie wiem na ile to
działa.

Pozdrawiam,
Wit Jakuczun