Cheapest Flights Within K Stops Medium 0 attempts
LeetCode ↗

Cheapest Flights Within K Stops

Medium GraphBFSDFS LeetCode

Find the cheapest price from source to destination with at most k stops in a flight network with n cities.

Example: n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1 → Output: 700

Sample Input
—
Sample Output
—
Constraints
  • 1 <= n <= 100
  • 0 <= flights.length <= n*(n-1)/2
  • 0 <= src, dst, k < n
  • 1 <= price <= 10^4
Test Cases
Case 1
Args: [4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1] Expected: 700
Topics
GraphBFSDFS

Bellman-Ford (K+1 iterations)

Relax edges K+1 times to find shortest path with at most K stops.

function findCheapestPrice(n, flights, src, dst, k) {
  let prices = Array(n).fill(Infinity);
  prices[src] = 0;
  for (let i = 0; i <= k; i++) {
    const temp = [...prices];
    for (const [u, v, w] of flights) {
      if (prices[u] !== Infinity) temp[v] = Math.min(temp[v], prices[u] + w);
    }
    prices = temp;
  }
  return prices[dst] === Infinity ? -1 : prices[dst];
}

Time: O(k * E) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript