Cheapest Flights within k Stops

Introduction

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from(i), to(i), price(i)] indicates that there is a flight from city from(i) to city to(i) with cost price(i).

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Solutions

1. Using Dijkstra's algorithm

main.py

from heapq import heappush, heappop
from collections import defaultdict
from typing import List


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

    priority_queue = [(0, src, k + 1)]  # (current_cost, current_city, remaining_stops)

    while priority_queue:
        current_cost, current_city, remaining_stops = heappop(priority_queue)

        if current_city == dst:
            return current_cost

        if remaining_stops > 0:
            for next_city, price in graph[current_city]:
                heappush(priority_queue, (current_cost + price, next_city, remaining_stops - 1))

    return -1

Introduction

Solutions

1. Using Dijkstra's algorithm

References