Cheapest Flights Within K Stops

Solution 1: Using Dijsktra algorithm

It's a direct application of the Dijkstra algorithm searching for minimum cost with a limiter number of moves. This number of moves is hence taken into account and the heap should be first sorted by number of moves and then by price.

from collections import defaultdict
import heapq

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    graph = defaultdict(list)
    for city_from, city_to, price in flights:
        graph[city_from].append((city_to, price))

    best_price = defaultdict(lambda: float('inf'))
    heap = [(0, 0, src)] # sort heap by number of stops and then by price
    heapq.heapify(heap)

    while heap:
        nb_stop, price, city = heapq.heappop(heap)
        if price < best_price[city] and nb_stop <= k+1:
            best_price[city] = price

            for city_to, price_to in graph[city]:
                heapq.heappush(heap, (nb_stop+1, price + price_to, city_to))

    if best_price[dst] != float('inf'):
        return(best_price[dst])
    else:
        return(-1)
        

Solution 2: Using Bellman-Ford algorithm

It's a direct application of the Bellman-Ford algorithm with a limiter number of moves.

from collections import defaultdict

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:   
    best_price = defaultdict(lambda: float('inf'))
    best_price[src] = 0

    # k possible stop hence k+1 flights
    for i in range(k+1):
        best_price_tmp = best_price.copy()
        for city_from, city_to, price in flights:
            best_price_tmp[city_to] = min(best_price_tmp[city_to], best_price[city_from] + price)
        best_price = best_price_tmp

    if best_price[dst] != float('inf'):
        return(best_price[dst])
    else:
        return(-1)