Witam, mam problem z zadaniem opartym na grafach. W skrócie chodzi o to, że muszę przedostać się z miasta pierwszego do miasta n-tego (ostatniego) w jak najkrótszym czasie. Jednak istnieją pewne połączenia, które nic nie kosztują (czas dotarcie z miasta A do miasta B jest równy 0). Takich połączeń jest maksymalnie 50. Jest ograniczenie, że nie można skorzystać z takich połączeń więcej niż k razy. (1<=k<=3)
Myślałem nad modyfikacją Dijkstry, ale to raczej nie wypali. Wpadłem na pomysł użycia algorytmu Floyda-Warshalla dla ścieżek o wadze > 0, a przechowywać ścieżki “zerowe” w jakiejś tablicy incydencji. Teraz mając “najkrótszą” ścieżkę z 1 do n (dzięki FW), to teraz chciałbym poprawić ścieżkę o te zerowe. Czy jest to dobry pomysł? Jeśli tak, to jak to robić? Czy może jednak trzeba do tego inaczej podejść?