Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Cheapest Flights Within K Stops
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

There are n cities connected by flights. You are given an array flights where flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>] indicates that there is a flight from city from<sub>i</sub> to city to<sub>i</sub> with cost price<sub>i</sub>.

Find the cheapest price from a src city to a dst city, but you are allowed to have at most k stops. If there is no such route, return -1.

Examples

Example 1:

  • Input: n = 5, flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [3, 4, 50], [0, 4, 300]], src = 1, dst = 4, k = 2
  • Expected Output: 150
Image
  • Explanation: The cheapest flight route from city 1 to city 4 with at most 2 stops is 1 -> 2 -> 3 -> 4. The total cost is 50 + 50 + 50 = 150.

Example 2:

  • Input: n = 4, flights = [[0, 1, 100], [1, 2, 200], [2, 3, 300], [0, 3, 500]], src = 0, dst = 3, k = 1
  • Expected Output: 500
Image
  • Explanation: The cheapest flight route from city 0 to city 3 with at most 1 stop is 0 -> 3. The total cost is 500.

Example 3:

  • Input: n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1
  • Expected Output: 200
Image
  • Explanation: The cheapest flight route from city 0 to city 2 with at most 1 stop is 0 -> 1 -> 2. The total cost is 100 + 100 = 200.

Constraints:

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= from<sub>i</sub>, to<sub>i</sub> < n
  • from<sub>i</sub> != to<sub>i</sub>
  • 1 <= price<sub>i</sub> <= 104
  • There will not be any multiple flights between two cities.
  • 0 <= src, dst, k < n
  • src != dst

Solution

To solve this problem, we need to find the least costly path from the source city to the destination city with a restriction on the number of stops. A good approach to solve this is using a modified Dijkstra's algorithm or a Breadth-First Search (BFS) with a priority queue to ensure we always explore the least costly paths first. The key difference is that we need to track the number of stops made and avoid exceeding the allowed stops.

This approach works effectively because it combines the efficiency of Dijkstra's algorithm for finding the shortest paths and the level-order exploration of BFS, which helps in handling the stop count constraint. By using a priority queue, we ensure that the paths are explored in the order of their costs, leading to an efficient solution that minimizes unnecessary computations.

Step-by-Step Algorithm

  1. Initialize Data Structures:

    • Create a priority queue to store flights as tuples (int city, int cost, int stops).
    • Use a dictionary to represent the graph, where each key is a city, and its value is a list of tuples representing destination cities and costs.

  2. Build the Graph:

    • Loop through the flights list and populate the graph dictionary with the flight data. Each flight is represented as a tuple (destination_city, price).

  3. Start from the Source:

    • Push the starting city src (with cost 0 and 0 stops) into the priority queue as new Flight(src, 0, 0).

  4. Explore the Flights:

    • While the priority queue is not empty:
      • Pop the cheapest flight option from the priority queue.
      • If the current city is the destination and the number of stops is within the limit, return the cost.
      • If the number of stops is within the limit, explore the neighboring cities:
        • Add new Flight(neighbor[0], current.cost + neighbor[1], current.stops + 1) to the priority queue. It is a new cost to reach to the neighbour[0] node.

  5. No Valid Route:

    • If the priority queue is exhausted without finding a valid route, return -1.

Sure, let's correct the algorithm walkthrough according to the provided Java code and the explanation.

Algorithm Walkthrough

Let's go through the steps with the given input: n = 5, flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [3, 4, 50], [0, 4, 300]], src = 1, dst = 4, k = 2.

Image

  1. Initialize Data Structures:

    • Priority Queue: []
    • Graph: {}

  2. Build the Graph:

    • Adding flight [0, 1, 50] -> Graph: {0: [(1, 50)]}
    • Adding flight [1, 2, 50] -> Graph: {0: [(1, 50)], 1: [(2, 50)]}
    • Adding flight [2, 3, 50] -> Graph: {0: [(1, 50)], 1: [(2, 50)], 2: [(3, 50)]}
    • Adding flight [3, 4, 50] -> Graph: {0: [(1, 50)], 1: [(2, 50)], 2: [(3, 50)], 3: [(4, 50)]}
    • Adding flight [0, 4, 300] -> Graph: {0: [(1, 50), (4, 300)], 1: [(2, 50)], 2: [(3, 50)], 3: [(4, 50)]}

  3. Start from the Source:

    • Push starting city src = 1 into the priority queue.
    • Priority Queue: [new Flight(1, 0, 0)] (city, cost, stops)

  4. Explore the Flights:

    • While Priority Queue is not empty:
      • Pop new Flight(1, 0, 0) from the priority queue.
      • Current flight: (1, 0, 0) (city: 1, cost: 0, stops: 0)
      • If current.city == dst (1 == 4) and stops <= k (0 <= 2): No, continue.
      • Explore neighbors of city 1: [(2, 50)]
        • For neighbor (2, 50): New cost = 0 + 50 = 50, stops = 0 + 1 = 1
        • Push new Flight(2, 50, 1) into priority queue.
        • Priority Queue: [new Flight(2, 50, 1)]
      • Pop new Flight(2, 50, 1) from the priority queue.
      • Current flight: (2, 50, 1) (city: 2, cost: 50, stops: 1)
      • If current.city == dst (2 == 4) and stops <= k (1 <= 2): No, continue.
      • Explore neighbors of city 2: [(3, 50)]
        • For neighbor (3, 50): New cost = 50 + 50 = 100, stops = 1 + 1 = 2
        • Push new Flight(3, 100, 2) into priority queue.
        • Priority Queue: [new Flight(3, 100, 2)]
      • Pop new Flight(3, 100, 2) from the priority queue.
      • Current flight: (3, 100, 2) (city: 3, cost: 100, stops: 2)
      • If current.city == dst (3 == 4) and stops <= k (2 <= 2): No, continue.
      • Explore neighbors of city 3: [(4, 50)]
        • For neighbor (4, 50): New cost = 100 + 50 = 150, stops = 2 + 1 = 3
        • Push new Flight(4, 150, 3) into priority queue.
        • Priority Queue: [new Flight(4, 150, 3)]
      • Pop new Flight(4, 150, 3) from the priority queue.
      • Current flight: (4, 150, 3) (city: 4, cost: 150, stops: 3)
      • If current.city == dst (4 == 4).
      • Since we reached to the destination node. Return 150.

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: O(n + E * K log(E * K)), where n is the number of nodes and E is the number of edges. Building the graph takes O(n). The priority queue operations take O( E * K log(E * K)) due to push and pop operations. Here, we can go through at most K nodes.
  • Space Complexity: O(n + E * K), where n is the number of nodes and E is the number of edges. This space is required for the graph and the priority queue.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible