Cheapest Flights Within K Stops

Leetcode Problem 787: Cheapest Flights Within K Stops

Problem Summary

There are n cities connected by directed flights, each with an associated cost. Given a source city, a destination city, and a maximum number of stops k, find the cheapest price to travel from source to destination using at most k intermediate stops. If no such route exists, return -1. The number of cities can be up to 100, flight costs range from 1 to 10,000, and the number of flights can be up to n * (n - 1) / 2. There are no multiple flights between the same pair of cities.

Techniques

Dynamic Programming
Depth-First Search
Breadth-First Search
Graph Theory
Heap (Priority Queue)
Shortest Path

Solution

type Edge = { node: number; cost: number };

type State = {
    node: number,
    cost: number,
    stops: number
}

function createGraph(flights: number[][], n: number) { 
    const graph: Edge[][] =  Array.from({ length: n }, () => []);

    for (const [u, v, w] of flights) {
        graph[u].push({ node: v, cost: w });
    }

    return graph;
}

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const graph = createGraph(flights, n);
    let head = 0;
    const queue: State[] = [{ node: src, cost: 0, stops: 0 }];
    const visited: number[][] = Array.from({ length: n }, () =>
        Array(k + 2).fill(Infinity)
    );
    visited[src][0] = 0;

    while (head < queue.length) {
        const { node, cost, stops } = queue[head++];
        
        if (node === dst) {
            continue;
        }

        if (stops > k) {
            continue;
        }

        for (const { node: next, cost: nextCost } of graph[node]) {
            const newCost = cost + nextCost
            const newStops = stops + 1

            if (newCost < visited[next][newStops]) {
                visited[next][newStops] = newCost
                queue.push({
                    node: next,
                    cost: newCost,
                    stops: newStops
                })
            }
        }
    }
    
    let answer = Infinity;
    for (let s = 0; s <= k + 1; s++) {
        answer = Math.min(answer, visited[dst][s]);
    }

    return answer === Infinity ? -1 : answer;
};

console.log(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)); // 200
console.log(findCheapestPrice(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0)); // 500