Zadanie na grafach (zmodyfikowana Dijkstra)

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 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.

Szukam sprytnego rozwiązania problemu, czegoś innego, niż sprawdzanie wszystkich możliwości, najpierw dla k=0,, potem k=1, 2, 3 (k <= 3), zwłaszcza, że mogą być takie dane, że się nie opłaca z nich korzystać. Wydaje mi się, że trzeba zmodyfikować algorytm Dijkstry, ale nie wiem jak zabrać się do tej modyfikacji. Jak uwzględnić w programie te ścieżki o wadze zerowej?

A może jednak rozszerzyć algorytm Dijkstry/Bellmana-Forda o kolejny krok zamiast kombinować z jakąś modyfiacją?

Mój pomysł:

1. Wyliczyć najpierw najkrótsze ścieżki w grafie z punktu startowego, nie uwzględniając tych zerowych przejść
2. Wyliczyć najkrótsze ścieżki dochodzące do punktu końcowego (czyli tak samo jak punkt wyżej, ale startujemy z końca i poruszamy się po krawędziach odwrotnie)
3. Dopiero teraz analizujemy czy używając któregoś z tych 0-przejść jesteśmy w stanie poprawić drogę. Z punktów 1 i 2 znamy kosz dojścia z punktu startowego do dowolnego wierzchołka, oraz z dowolnego wierzchołka do punktu końcowego. Możemy więc w O(1) dla dowolnego 0-przejścia policzyć nowy koszt trasy z uwzględnieniem tego skrótu. Tutaj niestety nie da rady już chyba nic poprawić i trzeba raczej wykładniczo przetestować dostepne możliwości, ale jeśli u ciebie k<4 to nie ma chyba jeszcze wielkiej tragedii.

akurat robię kurs na coursera.org o grafach, hehe.

Może chodzi Ci o A Star Search?

Algorytm Dijkstra jest szczególnym przypadkiem A* Search algorithm , gdzie drugi threshold mówiący o najlepszej przewidywanej drodze jest zawsze równy zero.

Ja bym proponował, żeby ustalić wagę jako parę (waga_realna, liczba_użytych_przejść_zerowych) i porównywać tak, że porównujemy wagi_realne tylko gdy liczba_użytych_przejść_zerowych <= k, natomiast gdy liczba_użytych_przejść_zerowych > k, traktujemy taką parę jak nieskończoność. No i prócz porównywania trzeba zdefiniować odpowiednio dodawanie i maksimum/minimum, ale to raczej proste. A, i jeszcze dane z grafu -- wszystkie wejściowe wagi dodatnie mają naszą wagę (waga, 0), a wszystkie wagi zerowe: (0, 1).

I powinno śmigać normalnym Dijkstrą.

A nie jest to problem znajdowania wszystkich ścieżek między para wierzchołków? Mając to można dla każdej ścieżki liczyć długość (czas) i odrzucać te, które przechodzą przez więcej niż K miast i zapamiętywać minimalną?
https://www.geeksforgeeks.org/find-paths-given-source-destination/

-- Edited:
przez więcej niż K połączeń 0, a nie miast.

Zawsze mozna skonstruowac (50 po 3) = 19600 grafow i odpalic na wszystkie dijkstre i wybrac ten z najkrotsza sciezka.

Jeszcze jest cos takiego jak incremental Dijkstra algorithm, ale jest dosc skomplikowany. Jezeli zadanie na prawde dotyczy big data to pewnie warto sprawdzic. Jezeli to zadanie na jakies OI to raczej watpie.

@Shalom: Czyli muszę użyć Floyda-Warshalla dla ścieżek o wadze != 0, potem znowu ten algorytm puścić, gdy mogę skorzystać z tylko z 1 ścieżki o wadze 0, potem z 2 ścieżek, na końcu z 3? Trzymać to w oddzielnych tablicach?

A może lepiej jak Floyd-Warshall powie mi, jak wygląda koszt przy ścieżkach > 0 z miasta pierwszego do ostatniego, potem patrzeć w tablicy z samymi ścieżkami zerowymi, gdzie mogę sobie skrócić najkorzystniej trasę (muszę jeszcze zapamiętywać przez jakie wierzchołki przechodziłem). Chociaż w sumie, może być taka sytuacja, że powinienem użyć takiego przejścia, że wskoczę na wierzchołek, który wcześniej nie był uwzględniony przy ścieżkach > 0.

Dla mnie odpalenie tego algorytmu ograniczającego do jednego nawet użycia takiej ścieżki o wadze 0 wydaje się dosyć trudne do zakodowania.

@Saradoc: mój pomysł to ta opcja numer 2. Tzn najpierw FW liczysz ścieżki między każdą parą, a potem dla trasy początek->koniec szukasz czy któreś 0-przejście nie daje ci lepszej trasy. Nie musisz liczyć FW kolejny raz już, bo użycie 0-przejścia A-B sprawia że nowy koszt to koszt początek->A + B->koniec