Cheapest Flights Within K Stops

Q: Jaka jest złożoność czasowa algorytmu Cheapest Flights Within K Stops?

Bellman-Ford ograniczony do k+1 rund działa w czasie O(k · E) dla E lotów i wymaga O(n) dodatkowej pamięci na dwie tablice cen. Runda, która niczego nie zmienia, przekazuje następnej rundzie te same ceny, więc możesz zakończyć wcześniej.

Q: Dlaczego algorytm Dijkstry nie działa w przypadku najtańszych lotów z maksymalnie K przesiadkami?

Dijkstra przechowuje najlepszą cenę dla każdego miasta i nigdy nie odwiedza ponownie miasta, którego najkrótsza droga została już ustalona. Tutaj droższa droga do miasta może być przydatna, jeśli wymagała mniejszej liczby lotów. Dijkstra znów działa na stanach (miasto, wykorzystane loty), co zwiększa liczbę stanów k+1 razy.

Q: Czy potrafisz rozwiązać problem „Najtańsze loty z maksymalnie K przesiadkami” za pomocą BFS?

Tak. Poziom r zawiera miasta osiągnięte dokładnie r lotami wraz z ich cenami. Umieść miasto na następnym poziomie tylko wtedy, gdy jego nowa cena jest niższa od najlepszej dotąd znalezionej, i zakończ po k+1 poziomach. Daje to tę samą odpowiedź co algorytm Bellmana-Forda, ale uwzględnia tylko loty z miast, których cena uległa zmianie.

ŚrednieNajkrótsze ścieżki Grafy

+10

Jest n miast, ponumerowanych od 0 do n-1, oraz lista lotów w jedną stronę: flights[i] = [from, to, price] oznacza lot z miasta from do miasta to, który kosztuje price.

Zwróć najniższą łączną cenę podróży z src do dst, która obejmuje najwyżej k przesiadek po drodze, czyli najwyżej k+1 lotów. Jeśli taka podróż nie istnieje, zwróć -1.

Funkcja

findCheapestPrice(n: integer, flights: integer-2d-array, src: integer, dst: integer, k: integer) → integer

ninteger: liczba miast
flightsinteger-2d-array: loty w jedną stronę, każdy jako [from, to, price]
srcinteger: miasto, w którym rozpoczyna się podróż
dstinteger: miasto, w którym kończy się podróż
kinteger: największa dozwolona liczba przystanków między src a dst
Zwracainteger: najniższa cena podróży z co najwyżej k przesiadkami lub -1

Ograniczenia

2 ≤ n ≤ 1000
1 ≤ flights.length ≤ 4500
flights[i] = [from, to, price] przy 0 ≤ from, to < n oraz from ≠ to
1 ≤ price ≤ 10⁴
Żadne dwa loty nie mają jednocześnie takiego samego from i to.
0 ≤ src, dst < n i src ≠ dst
0 ≤ k < n

Przykłady

Wejście: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
Wyjście: 230
Wyjaśnienie: Jeden przystanek pozwala na dwa loty: 0 → 1 → 3 kosztuje 50 + 180 = 230, a 0 → 2 → 3 kosztuje 200 + 50 = 250. Tańsza trasa 0 → 1 → 2 → 3 obejmuje dwa przystanki.

Wejście: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
Wyjście: 150
Wyjaśnienie: Dwa przystanki pozwalają na trzy loty, więc 0 → 1 → 2 → 3 jest teraz dozwolone, a koszt wynosi 50 + 50 + 50 = 150.

Pytanie dodatkowe

Jak zwrócić miasta na najtańszej trasie oraz jej cenę?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

To najkrótsza ścieżka z ograniczeniem liczby lotów. Algorytm Dijkstry zastosowany wyłącznie do miast nie sprawdza się, ponieważ najtańsza droga do miasta może zużyć przesiadki potrzebne na pozostałą część podróży. Bellman-Ford uwzględnia to ograniczenie: runda r wyznacza najniższą cenę przy maksymalnie r lotach, więc wykonujesz k+1 rund.

Wypróbuj każdą trasę z najwyżej k+1 lotami

Poprawne, ale nie kończy się na największych testach

Intuicja

Przejdź każdą trasę z src, używając stosu zawierającego (miasto, cenę, wykorzystane loty). Trasa, która dociera do dst, zapisuje swoją cenę i kończy się, ponieważ każda cena jest dodatnia. Trasa z k+1 lotami zostaje odrzucona; każda inna jest rozszerzana o wszystkie loty z jej miasta. Powstaje każda dozwolona podróż, więc najniższa z zapisanych cen jest poprawna.

Liczba tras rośnie jak d do potęgi k+1, gdzie d to liczba lotów z danego miasta. Przy 4 lotach z każdego miasta i k = 29 daje to 4^30 ≈ 1.2 × 10^18 tras.

Algorytm

Pogrupuj loty według miasta wylotu.
Umieść na stosie (src, 0, 0): miasto, dotychczasową cenę, liczbę odbytych lotów.
Zdejmij trasę ze stosu. Jeśli jej miastem jest dst, zachowaj jej cenę, jeśli jest najlepsza do tej pory.
W przeciwnym razie, jeśli odbyto mniej niż k+1 lotów, umieść na stosie po jednej dłuższej trasie dla każdego lotu z tego miasta.
Gdy stos będzie pusty, zwróć najlepszą cenę lub -1, jeśli żadna trasa nie dotarła do dst.

def findCheapestPrice(n, flights, src, dst, k):
    out = [[] for _ in range(n)]
    for a, b, price in flights:
        out[a].append((b, price))
    best = -1
    # Each entry is a route in progress: (city, price so far, flights taken).
    stack = [(src, 0, 0)]
    while stack:
        city, cost, used = stack.pop()
        if city == dst:
            if best == -1 or cost < best:
                best = cost
            continue
        # k stops allow at most k+1 flights.
        if used == k + 1:
            continue
        for nxt, price in out[city]:
            stack.append((nxt, cost + price, used + 1))
    return best

Bellman-Ford ograniczony do k+1 rund

Intuicja

Niech cost[c] oznacza najniższą cenę dotarcia do miasta c przy użyciu co najwyżej r lotów. Dla r = 0 osiągalne jest tylko src, a cena wynosi 0. Podróż do a przy użyciu co najwyżej r lotów, po której następuje lot a → b, jest podróżą do b przy użyciu co najwyżej r+1 lotów, więc każda runda oferuje cenę cost[a] + price dla b na każdym locie. Po k+1 rundach cost[dst] jest odpowiedzią.

Każda runda odczytuje ceny z poprzedniej rundy i zapisuje wyniki do kopii, więc cena ustawiona w trakcie rundy nie może posłużyć do wykonania kolejnego lotu w tej samej rundzie. W pierwszym przykładzie, dla k = 1, cena miasta 2 spada do 100 w rundzie 2, ale nie ma już rundy, by polecieć dalej do miasta 3 za 150.

Każda runda odczytuje każdy lot jeden raz: czas O(k · E) dla E lotów i przestrzeń O(n) dla dwóch tablic.

Algorytm

Ustaw cost[src] = 0, a każdą inną wartość cost ustaw na nieskończoność.
Powtórz k+1 razy: skopiuj cost do next.
Dla każdego lotu [a, b, price], gdy cost[a] jest skończone, jeśli cost[a] + price < next[b], ustaw next[b] = cost[a] + price.
Zastąp cost przez next i zakończ wcześniej, jeśli nic się nie zmieniło.
Zwróć cost[dst] lub -1, jeśli nadal wynosi nieskończoność.

def findCheapestPrice(n, flights, src, dst, k):
    INF = float("inf")
    # cost[c]: the cheapest price to reach city c with the flights allowed so far.
    cost = [INF] * n
    cost[src] = 0
    # Each round allows one more flight; k stops means k+1 flights.
    for _ in range(k + 1):
        # Read last round's prices and write into a copy,
        # so one round can never chain two flights.
        nxt = cost[:]
        changed = False
        for a, b, price in flights:
            if cost[a] != INF and cost[a] + price < nxt[b]:
                nxt[b] = cost[a] + price
                changed = True
        cost = nxt
        if not changed:
            break
    return -1 if cost[dst] == INF else cost[dst]

Pułapki i przypadki brzegowe

Liczenie przystanków jako lotów. k przystanków oznacza k+1 lotów i k+1 rund.
Aktualizowanie w miejscu. Przy 0 → 1, 1 → 2, 2 → 3 za 1 każdy, w tej kolejności, oraz 0 → 3 za 500 i k = 0, jedna runda łączy trzy loty i zwraca 3, a nie 500.
Uruchamianie zwykłego algorytmu Dijkstry dla miast. Przy 0 → 1 i 1 → 2 za 1 każdy, 0 → 2 za 40, 2 → 3 za 1 i k = 1, algorytm ustala koszt dotarcia do miasta 2 na 2 po dwóch lotach i pomija trasę 0 → 2 → 3 za 41.
Wylatywanie z miasta, do którego jeszcze nie dotarto. Gdy nieskończoność jest największą wartością typu int, cost[a] + price przepełnia się do wartości ujemnej w 32 bitach. Najpierw sprawdź, czy cost[a] jest skończone.

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu Cheapest Flights Within K Stops?

Bellman-Ford ograniczony do k+1 rund działa w czasie O(k · E) dla E lotów i wymaga O(n) dodatkowej pamięci na dwie tablice cen. Runda, która niczego nie zmienia, przekazuje następnej rundzie te same ceny, więc możesz zakończyć wcześniej.

Dlaczego algorytm Dijkstry nie działa w przypadku najtańszych lotów z maksymalnie K przesiadkami?

Dijkstra przechowuje najlepszą cenę dla każdego miasta i nigdy nie odwiedza ponownie miasta, którego najkrótsza droga została już ustalona. Tutaj droższa droga do miasta może być przydatna, jeśli wymagała mniejszej liczby lotów. Dijkstra znów działa na stanach (miasto, wykorzystane loty), co zwiększa liczbę stanów k+1 razy.

Czy potrafisz rozwiązać problem „Najtańsze loty z maksymalnie K przesiadkami” za pomocą BFS?

Tak. Poziom r zawiera miasta osiągnięte dokładnie r lotami wraz z ich cenami. Umieść miasto na następnym poziomie tylko wtedy, gdy jego nowa cena jest niższa od najlepszej dotąd znalezionej, i zakończ po k+1 poziomach. Daje to tę samą odpowiedź co algorytm Bellmana-Forda, ale uwzględnia tylko loty z miast, których cena uległa zmianie.

def findCheapestPrice(n, flights, src, dst, k):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

n = 4
flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]
src = 0
dst = 3
k = 1

Oczekiwany wynik