Cheapest Flights Within K Stops

Q: Wie hoch ist die Zeitkomplexität von „Cheapest Flights Within K Stops“?

Bellman-Ford benötigt bei Beschränkung auf k+1 Runden O(k · E) Zeit für E Flüge und O(n) zusätzlichen Speicherplatz für zwei Preisarrays. Eine Runde, in der sich nichts ändert, übergibt der nächsten Runde dieselben Preise, sodass du vorzeitig abbrechen kannst.

Q: Warum funktioniert Dijkstras Algorithmus nicht für die günstigsten Flüge mit höchstens K Zwischenstopps?

Dijkstra behält einen besten Preis pro Stadt bei und besucht eine endgültig festgelegte Stadt nicht erneut. Hier kann ein teurerer Weg in eine Stadt der nützlichere sein, wenn er weniger Flüge benötigt hat. Dijkstra funktioniert wieder mit Zuständen (Stadt, genutzte Flüge), wodurch sich die Anzahl der Zustände mit k+1 vervielfacht.

Q: Kannst du „Cheapest Flights Within K Stops“ mit BFS lösen?

Ja. Ebene r enthält die Städte, die mit genau r Flügen erreicht wurden, sowie deren Preise. Nimm eine Stadt nur dann in die nächste Ebene auf, wenn ihr neuer Preis den bislang besten für sie unterbietet, und höre nach k+1 Ebenen auf. Das Ergebnis ist dasselbe wie bei Bellman-Ford, aber es werden nur Flüge von Städten aus verfolgt, deren Preis sich geändert hat.

MittelKürzeste Wege Graphen

+10

Es gibt n Städte, nummeriert von 0 bis n-1, und eine Liste von Einwegflügen: flights[i] = [from, to, price] ist ein Flug von Stadt from nach Stadt to, der price kostet.

Gib den niedrigsten Gesamtpreis für eine Reise von src nach dst zurück, bei der es unterwegs höchstens k Zwischenstopps gibt, was höchstens k+1 Flügen entspricht. Wenn es keine solche Reise gibt, gib -1 zurück.

Funktion

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

ninteger: die Anzahl der Städte
flightsinteger-2d-array: die Einwegflüge, jeweils als [from, to, price]
srcinteger: die Stadt, in der die Reise beginnt
dstinteger: die Stadt, in der die Reise endet
kinteger: die meisten zulässigen Haltestellen zwischen src und dst
Gibt zurückinteger: der niedrigste Preis einer Reise mit höchstens k Zwischenstopps oder -1

Einschränkungen

2 ≤ n ≤ 1000
1 ≤ flights.length ≤ 4500
flights[i] = [from, to, price] mit 0 ≤ from, to < n und from ≠ to
1 ≤ price ≤ 10⁴
Keine zwei Flüge haben dieselben Werte für from und to.
0 ≤ src, dst < n und src ≠ dst
0 ≤ k < n

Beispiele

Eingabe: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
Ausgabe: 230
Erklärung: Ein Zwischenstopp erlaubt zwei Flüge: 0 → 1 → 3 kostet 50 + 180 = 230 und 0 → 2 → 3 kostet 200 + 50 = 250. Die günstigere Route 0 → 1 → 2 → 3 umfasst zwei Zwischenstopps.

Eingabe: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
Ausgabe: 150
Erklärung: Zwei Zwischenstopps ermöglichen drei Flüge, daher ist 0 → 1 → 2 → 3 jetzt erlaubt und kostet 50 + 50 + 50 = 150.

Weiterführende Frage

Wie würdest du die Städte der günstigsten Reise sowie ihren Preis zurückgeben?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Dies ist ein kürzester Weg mit einer Begrenzung der Anzahl der Flüge. Dijkstras Algorithmus, der nur die Städte berücksichtigt, schlägt fehl, weil der günstigste Weg in eine Stadt möglicherweise Zwischenstopps verbraucht, die der Rest der Reise benötigt. Bellman-Ford eignet sich für diese Begrenzung: In Runde r wird der günstigste Preis mit höchstens r Flügen ermittelt, also führst du k+1 Runden aus.

Probiere jede Route mit höchstens k+1 Flügen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Durchlaufe jede Route ab src mit einem Stack aus (Stadt, Preis, genutzte Flüge). Eine Route, die dst erreicht, hält ihren Preis fest und endet, da jeder Preis positiv ist. Eine Route mit k+1 Flügen wird verworfen; jede andere wird um jeden Flug erweitert, der von ihrer Stadt ausgeht. Jede zulässige Reise wird aufgebaut, daher ist der niedrigste festgehaltene Preis korrekt.

Die Anzahl der Routen wächst wie d hoch k+1, wenn d Flüge von einer Stadt ausgehen. Bei 4 Flügen pro Stadt und k = 29 sind das 4^30 ≈ 1.2 × 10^18 Routen.

Algorithmus

Gruppiere die Flüge nach Abflugstadt.
Lege (src, 0, 0) auf den Stapel: Stadt, bisheriger Preis, absolvierte Flüge.
Nimm eine Route vom Stapel. Wenn ihre Stadt dst ist, speichere ihren Preis, falls er bisher der beste ist.
Andernfalls lege, wenn sie weniger als k+1 Flüge absolviert hat, für jeden Flug aus ihrer Stadt eine um einen Flug längere Route auf den Stapel.
Wenn der Stapel leer ist, gib den besten Preis zurück oder -1, falls keine Route dst erreicht hat.

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 auf k+1 Runden begrenzt

Idee

Sei cost[c] der günstigste Preis, um Stadt c mit höchstens r Flügen zu erreichen. Bei r = 0 ist nur src zum Preis von 0 erreichbar. Eine Reise nach a mit höchstens r Flügen, gefolgt von einem Flug a → b, ist eine Reise nach b mit höchstens r+1 Flügen. Daher wird in jeder Runde für jeden Flug cost[a] + price als Preis für b angeboten. Nach k+1 Runden ist cost[dst] die Antwort.

In jeder Runde werden die Preise der vorherigen Runde gelesen und in eine Kopie geschrieben, sodass ein während einer Runde festgelegter Preis nicht im selben Durchlauf für einen weiteren Flug verwendet werden kann. Im ersten Beispiel sinkt der Preis für Stadt 2 in Runde 2 auf 100, aber es bleibt keine Runde mehr, um nach Stadt 3 für 150 weiterzufliegen.

In jeder Runde wird jeder Flug einmal verarbeitet: Laufzeit O(k · E) für E Flüge und Speicherbedarf O(n) für die beiden Arrays.

Algorithmus

Setze cost[src] = 0 und alle anderen cost auf unendlich.
Wiederhole k+1 Mal: Kopiere cost in next.
Gehe jeden Flug [a, b, price] durch, für den cost[a] endlich ist. Falls cost[a] + price < next[b], setze next[b] = cost[a] + price.
Ersetze cost durch next und brich vorzeitig ab, wenn sich nichts geändert hat.
Gib cost[dst] zurück oder -1, falls der Wert weiterhin unendlich ist.

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]

Stolperfallen und Grenzfälle

Zwischenstopps als Flüge zählen. k Zwischenstopps bedeuten k+1 Flüge und k+1 Runden.
Direktes Aktualisieren. Bei 0 → 1, 1 → 2, 2 → 3 für jeweils 1, in dieser Reihenfolge, sowie 0 → 3 für 500 und k = 0 verkettet eine Runde drei Flüge und gibt 3 zurück, nicht 500.
Gewöhnliches Dijkstra auf Städten ausführen. Bei 0 → 1 und 1 → 2 für jeweils 1, 0 → 2 für 40, 2 → 3 für 1 und k = 1 erreicht der Algorithmus Stadt 2 nach zwei Flügen mit Kosten 2 und verpasst 0 → 2 → 3 für 41.
Von einer nicht erreichten Stadt abfliegen. Wenn unendlich als größte Ganzzahl verwendet wird, läuft cost[a] + price bei 32 Bit negativ über. Prüfe zuerst, ob cost[a] endlich ist.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Cheapest Flights Within K Stops“?

Bellman-Ford benötigt bei Beschränkung auf k+1 Runden O(k · E) Zeit für E Flüge und O(n) zusätzlichen Speicherplatz für zwei Preisarrays. Eine Runde, in der sich nichts ändert, übergibt der nächsten Runde dieselben Preise, sodass du vorzeitig abbrechen kannst.

Warum funktioniert Dijkstras Algorithmus nicht für die günstigsten Flüge mit höchstens K Zwischenstopps?

Dijkstra behält einen besten Preis pro Stadt bei und besucht eine endgültig festgelegte Stadt nicht erneut. Hier kann ein teurerer Weg in eine Stadt der nützlichere sein, wenn er weniger Flüge benötigt hat. Dijkstra funktioniert wieder mit Zuständen (Stadt, genutzte Flüge), wodurch sich die Anzahl der Zustände mit k+1 vervielfacht.

Kannst du „Cheapest Flights Within K Stops“ mit BFS lösen?

Ja. Ebene r enthält die Städte, die mit genau r Flügen erreicht wurden, sowie deren Preise. Nimm eine Stadt nur dann in die nächste Ebene auf, wenn ihr neuer Preis den bislang besten für sie unterbietet, und höre nach k+1 Ebenen auf. Das Ergebnis ist dasselbe wie bei Bellman-Ford, aber es werden nur Flüge von Städten aus verfolgt, deren Preis sich geändert hat.

def findCheapestPrice(n, flights, src, dst, k):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe