Cheapest Flights Within K Stops

Q: Quelle est la complexité temporelle de « Cheapest Flights Within K Stops » ?

Bellman-Ford limité à k+1 tours prend un temps de O(k · E) pour E vols, et nécessite O(n) espace supplémentaire pour deux tableaux de prix. Un tour qui ne change rien transmet les mêmes prix au tour suivant ; tu peux donc t’arrêter plus tôt.

Q: Pourquoi l’algorithme de Dijkstra ne fonctionne-t-il pas pour le problème des vols les moins chers avec au plus K escales ?

Dijkstra conserve le meilleur prix par ville et ne revisite jamais une ville dont le coût a été fixé. Ici, un trajet plus cher jusqu’à une ville peut être utile s’il a nécessité moins de vols. Dijkstra fonctionne à nouveau sur des états (ville, vols utilisés), ce qui multiplie le nombre d’états par k+1 .

Q: Peux-tu résoudre le problème « Cheapest Flights Within K Stops » avec un parcours en largeur (BFS) ?

Oui. Le niveau r contient les villes atteintes en exactement r vols, avec leurs prix. Place une ville au niveau suivant uniquement lorsque son nouveau prix est inférieur au meilleur prix déjà trouvé pour elle, et arrête-toi après k+1 niveaux. Cela donne le même résultat que Bellman-Ford, mais ne suit que les vols au départ des villes dont le prix a changé.

MoyenPlus courts chemins Graphes

+10

Il y a n villes, numérotées de 0 à n-1, et une liste de vols aller simple : flights[i] = [from, to, price] est un vol de la ville from à la ville to qui coûte price.

Renvoie le prix total le plus bas d’un trajet de src à dst comportant au maximum k escales, c’est-à-dire au maximum k+1 vols. Si aucun trajet de ce type n’existe, renvoie -1.

Fonction

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

ninteger: le nombre de villes
flightsinteger-2d-array: les vols aller simple, chacun sous la forme [from, to, price]
srcinteger: la ville où commence le voyage
dstinteger: la ville où le voyage se termine
kinteger: le plus grand nombre d’arrêts autorisés entre src et dst
Renvoieinteger: le prix le plus bas d’un trajet avec au plus k arrêts, ou -1

Contraintes

2 ≤ n ≤ 1000
1 ≤ flights.length ≤ 4500
flights[i] = [from, to, price] avec 0 ≤ from, to < n et from ≠ to
1 ≤ price ≤ 10⁴
Il n’existe pas deux vols ayant à la fois le même from et le même to.
0 ≤ src, dst < n et src ≠ dst
0 ≤ k < n

Exemples

Entrée: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
Sortie: 230
Explication: Une escale permet deux vols : 0 → 1 → 3 coûte 50 + 180 = 230 et 0 → 2 → 3 coûte 200 + 50 = 250. L’itinéraire moins cher 0 → 1 → 2 → 3 comporte deux escales.

Entrée: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
Sortie: 150
Explication: Deux escales permettent trois vols, donc 0 → 1 → 2 → 3 est maintenant autorisé, et cela coûte 50 + 50 + 50 = 150.

Pour aller plus loin

Comment retourner les villes du trajet le moins cher ainsi que son prix ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Il s’agit d’un plus court chemin avec une limite sur le nombre de vols. L’algorithme de Dijkstra appliqué aux seules villes échoue, car le moyen le moins cher d’arriver dans une ville peut consommer des escales dont le reste du trajet a besoin. Bellman-Ford s’adapte à cette limite : le tour r trouve le prix le plus bas avec au plus r vols, donc on exécute k+1 tours.

Essayez chaque itinéraire avec au plus k+1 vols

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Parcours chaque itinéraire depuis src avec une pile contenant (ville, prix, vols utilisés). Un itinéraire qui atteint dst enregistre son prix et se termine, puisque chaque prix est positif. Un itinéraire comportant k+1 vols est éliminé ; tout autre est prolongé par chaque vol au départ de sa ville. Tous les trajets autorisés sont construits, donc le meilleur prix enregistré est le bon.

Le nombre d’itinéraires croît comme d à la puissance k+1, pour d vols au départ d’une ville. Avec 4 vols par ville et k = 29, cela représente 4^30 ≈ 1.2 × 10^18 itinéraires.

Algorithme

Regroupez les vols par ville de départ.
Empilez (src, 0, 0) : la ville, le prix accumulé, le nombre de vols effectués.
Dépilez un itinéraire. Si sa ville est dst, conservez son prix s’il s’agit du meilleur jusqu’ici.
Sinon, s’il a effectué moins de k+1 vols, empilez un itinéraire plus long pour chaque vol au départ de sa ville.
Lorsque la pile est vide, renvoyez le meilleur prix, ou -1 si aucun itinéraire n’a atteint 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 limité à k+1 tours

Intuition

Soit cost[c] le prix le plus bas pour atteindre la ville c avec au plus r vols. À r = 0, seule src est accessible, au prix de 0. Un trajet jusqu’à a avec au plus r vols, suivi d’un vol a → b, est un trajet jusqu’à b avec au plus r+1 vols ; chaque tour propose donc cost[a] + price à b pour chaque vol. Après k+1 tours, cost[dst] est la réponse.

Chaque tour lit les prix du tour précédent et écrit dans une copie, de sorte qu’un prix fixé pendant un tour ne peut pas servir à prendre un autre vol au cours du même tour. Dans le premier exemple avec k = 1, le prix pour la ville 2 descend à 100 au tour 2, mais il ne reste aucun tour pour poursuivre jusqu’à la ville 3 au prix de 150.

Chaque tour parcourt chaque vol une fois : O(k · E) en temps pour E vols, et O(n) en espace pour les deux tableaux.

Algorithme

Définissez cost[src] = 0 et toutes les autres valeurs de cost à l’infini.
Répétez k+1 fois : copiez cost dans next.
Pour chaque vol [a, b, price] où cost[a] est fini, si cost[a] + price < next[b], définissez next[b] = cost[a] + price.
Remplacez cost par next, et arrêtez-vous plus tôt si rien n’a changé.
Renvoyez cost[dst], ou -1 s’il est toujours égal à l’infini.

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]

Pièges et cas limites

Compter les escales comme des vols. k escales signifie k+1 vols et k+1 tours.
Mettre à jour sur place. Avec 0 → 1, 1 → 2, 2 → 3 pour 1 chacun, dans cet ordre, ainsi que 0 → 3 pour 500 et k = 0, un tour enchaîne trois vols et renvoie 3, pas 500.
Exécuter Dijkstra classique sur les villes. Avec 0 → 1 et 1 → 2 pour 1 chacun, 0 → 2 pour 40, 2 → 3 pour 1 et k = 1, l’algorithme valide la ville 2 au coût de 2 après deux vols et ne trouve pas 0 → 2 → 3 pour 41.
Partir d’une ville qui n’a pas été atteinte. Avec l’infini comme plus grand entier, cost[a] + price déborde et devient négatif sur 32 bits. Vérifiez d’abord que cost[a] est fini.

Questions fréquentes3

Quelle est la complexité temporelle de « Cheapest Flights Within K Stops » ?

Bellman-Ford limité à k+1 tours prend un temps de O(k · E) pour E vols, et nécessite O(n) espace supplémentaire pour deux tableaux de prix. Un tour qui ne change rien transmet les mêmes prix au tour suivant ; tu peux donc t’arrêter plus tôt.

Pourquoi l’algorithme de Dijkstra ne fonctionne-t-il pas pour le problème des vols les moins chers avec au plus K escales ?

Dijkstra conserve le meilleur prix par ville et ne revisite jamais une ville dont le coût a été fixé. Ici, un trajet plus cher jusqu’à une ville peut être utile s’il a nécessité moins de vols. Dijkstra fonctionne à nouveau sur des états (ville, vols utilisés), ce qui multiplie le nombre d’états par k+1.

Peux-tu résoudre le problème « Cheapest Flights Within K Stops » avec un parcours en largeur (BFS) ?

Oui. Le niveau r contient les villes atteintes en exactement r vols, avec leurs prix. Place une ville au niveau suivant uniquement lorsque son nouveau prix est inférieur au meilleur prix déjà trouvé pour elle, et arrête-toi après k+1 niveaux. Cela donne le même résultat que Bellman-Ford, mais ne suit que les vols au départ des villes dont le prix a changé.

def findCheapestPrice(n, flights, src, dst, k):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu