Cheapest Flights Within K Stops

Q: Qual è la complessità temporale di «Cheapest Flights Within K Stops»?

Bellman-Ford limitato a k+1 round richiede un tempo O(k · E) per E voli e O(n) spazio aggiuntivo per due array di prezzi. Un round che non modifica nulla passa al round successivo gli stessi prezzi, quindi puoi fermarti in anticipo.

Q: Perché l'algoritmo di Dijkstra non funziona per i voli più economici con al massimo K scali?

Dijkstra mantiene un prezzo migliore per ogni città e non torna mai su una città già consolidata. In questo caso, una strada più costosa per raggiungere una città può rivelarsi utile, se ha richiesto meno voli. Dijkstra funziona di nuovo sugli stati (città, voli utilizzati), moltiplicando gli stati per k+1 .

Q: Riesci a risolvere «Voli più economici con al massimo K scali» usando BFS?

Sì. Il livello r contiene le città raggiunte con esattamente r voli, insieme ai relativi prezzi. Inserisci una città nel livello successivo solo quando il suo nuovo prezzo è inferiore al migliore trovato finora per quella città, e fermati dopo k+1 livelli. Fornisce la stessa risposta di Bellman-Ford, ma considera solo i voli in partenza dalle città il cui prezzo è cambiato.

MedioCammini minimi Grafi

+10

Ci sono n città, numerate da 0 a n-1, e un elenco di voli di sola andata: flights[i] = [from, to, price] è un volo dalla città from alla città to che costa price.

Restituisci il prezzo totale più basso per un viaggio da src a dst con al massimo k scali, ovvero al massimo k+1 voli. Se non esiste un viaggio del genere, restituisci -1.

Funzione

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

ninteger: il numero di città
flightsinteger-2d-array: i voli di sola andata, ciascuno come [from, to, price]
srcinteger: la città da cui parte il viaggio
dstinteger: la città in cui termina il viaggio
kinteger: il numero massimo di fermate consentite tra src e dst
Restituisceinteger: il prezzo più basso di un viaggio con al massimo k fermate, oppure -1

Vincoli

2 ≤ n ≤ 1000
1 ≤ flights.length ≤ 4500
flights[i] = [from, to, price] con 0 ≤ from, to < n e from ≠ to
1 ≤ price ≤ 10⁴
Non ci sono due voli che condividano sia from sia to.
0 ≤ src, dst < n e src ≠ dst
0 ≤ k < n

Esempi

Input: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
Output: 230
Spiegazione: Uno scalo consente due voli: 0 → 1 → 3 costa 50 + 180 = 230 e 0 → 2 → 3 costa 200 + 50 = 250. Il percorso più economico, 0 → 1 → 2 → 3, fa due scali.

Input: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
Output: 150
Spiegazione: Due fermate consentono tre voli, quindi ora è consentito 0 → 1 → 2 → 3 e costa 50 + 50 + 50 = 150.

Per approfondire

Come restituiresti le città del viaggio più economico e il suo prezzo?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Questo è un percorso più breve con un limite al numero di voli. L'algoritmo di Dijkstra sulle sole città non funziona, perché il modo più economico per arrivare in una città potrebbe consumare scali necessari per il resto del viaggio. Bellman-Ford rispetta il limite: il round r trova il prezzo più basso con al massimo r voli, quindi esegui k+1 round.

Prova ogni percorso con al massimo k+1 voli

Corretto, ma non termina sui test più grandi

Intuizione

Percorri ogni percorso da src usando uno stack di (città, prezzo, voli utilizzati). Un percorso che raggiunge dst registra il suo prezzo e termina, poiché ogni prezzo è positivo. Un percorso con k+1 voli viene scartato; ogni altro viene esteso con tutti i voli in partenza dalla sua città. Vengono costruiti tutti i viaggi consentiti, quindi il miglior prezzo registrato è corretto.

I percorsi crescono come d elevato alla potenza k+1, per d voli in partenza da una città. Con 4 voli per città e k = 29, si ottengono 4^30 ≈ 1.2 × 10^18 percorsi.

Algoritmo

Raggruppa i voli per città di partenza.
Aggiungi (src, 0, 0): città, prezzo finora, voli effettuati.
Estrai un percorso. Se la sua città è dst, conserva il suo prezzo se è il migliore finora.
Altrimenti, se ha effettuato meno di k+1 voli, aggiungi un percorso più lungo per ogni volo in partenza dalla sua città.
Quando lo stack è vuoto, restituisci il prezzo migliore, oppure -1 se nessun percorso ha raggiunto 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 limitato a k+1 iterazioni

Intuizione

Sia cost[c] il prezzo più basso per raggiungere la città c con al massimo r voli. Con r = 0 è raggiungibile solo src, al prezzo di 0. Un viaggio fino ad a con al massimo r voli, seguito da un volo a → b, è un viaggio fino a b con al massimo r+1 voli, quindi a ogni iterazione si propone a b il prezzo cost[a] + price per ogni volo. Dopo k+1 iterazioni, cost[dst] è la risposta.

A ogni iterazione si leggono i prezzi dell'iterazione precedente e si scrive in una copia, quindi un prezzo impostato durante un'iterazione non può alimentare un altro volo nella stessa iterazione. Nel primo esempio con k = 1, il prezzo per la città 2 scende a 100 nell'iterazione 2, ma non resta nessuna iterazione per proseguire in volo fino alla città 3 al prezzo di 150.

A ogni iterazione si legge ogni volo una volta: tempo O(k · E) per E voli e spazio O(n) per i due array.

Algoritmo

Imposta cost[src] = 0 e ogni altro cost a infinito.
Ripeti k+1 volte: copia cost in next.
Per ogni volo [a, b, price] per cui cost[a] è finito, se cost[a] + price < next[b], imposta next[b] = cost[a] + price.
Sostituisci cost con next e interrompi in anticipo se non è cambiato nulla.
Restituisci cost[dst], oppure -1 se è ancora infinito.

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]

Trappole e casi limite

Contare le fermate come voli. k fermate significano k+1 voli e k+1 round.
Aggiornare sul posto. Con 0 → 1, 1 → 2, 2 → 3 a 1 ciascuno, in quest'ordine, più 0 → 3 a 500 e k = 0, un round concatena tre voli e restituisce 3, non 500.
Eseguire Dijkstra semplice sulle città. Con 0 → 1 e 1 → 2 a 1 ciascuno, 0 → 2 a 40, 2 → 3 a 1 e k = 1, stabilizza la città 2 a 2 dopo due voli e non considera 0 → 2 → 3 a 41.
Partire da una città non raggiunta. Se l'infinito è il valore int più grande, cost[a] + price diventa negativo con un overflow a 32 bit. Verifica prima che cost[a] sia finito.

Domande frequenti3

Qual è la complessità temporale di «Cheapest Flights Within K Stops»?

Bellman-Ford limitato a k+1 round richiede un tempo O(k · E) per E voli e O(n) spazio aggiuntivo per due array di prezzi. Un round che non modifica nulla passa al round successivo gli stessi prezzi, quindi puoi fermarti in anticipo.

Perché l'algoritmo di Dijkstra non funziona per i voli più economici con al massimo K scali?

Dijkstra mantiene un prezzo migliore per ogni città e non torna mai su una città già consolidata. In questo caso, una strada più costosa per raggiungere una città può rivelarsi utile, se ha richiesto meno voli. Dijkstra funziona di nuovo sugli stati (città, voli utilizzati), moltiplicando gli stati per k+1.

Riesci a risolvere «Voli più economici con al massimo K scali» usando BFS?

Sì. Il livello r contiene le città raggiunte con esattamente r voli, insieme ai relativi prezzi. Inserisci una città nel livello successivo solo quando il suo nuovo prezzo è inferiore al migliore trovato finora per quella città, e fermati dopo k+1 livelli. Fornisce la stessa risposta di Bellman-Ford, ma considera solo i voli in partenza dalle città il cui prezzo è cambiato.

def findCheapestPrice(n, flights, src, dst, k):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso