< Back





787. Cheapest Flights Within K Stops

Another Dijkstra's algorithm question, which is fun. This time, distance still matters and will be
minimized via the min-heap, however, we're concerned about the number of stops it takes to reach the
destination. We're given a variable, k, which is the maximum number of stops we can take to reach
a given destination, dst, from a source, src. If we can't reach the destination, we return -1. If
we can before hitting k stops, we return the minimum cost.

Unlike most Dijkstra's algorithm questions, instead of maintaining a distances array where each
index, i, corresponds to a node and keeps track of the minimum distance, we create a stops array
where that keeps track of the minimum number of stops required to reach node i. This allows us to
stop traversing a path in the algorithm if the number of stops taken so far for a path exceed k, or
if the path is suboptimal in comparison to the known shortest path to the current node.

We conduct our search as usual, updating the amount of stops it takes for a node as we pop it off of
the heap. Of course, if the number of stops for this entry is greater than the number of stops
previously seen for this node, we skip. Same goes for if the number of stops exceeds k. If we visit
the dst node, we immediately return the current distance - we've found the minimum cost to reach
dst. Otherwise, we push the neighboring nodes into the heap, updating distance and number of stops.

Eventually we'll find the dst and the minimum cost - if we don't we just return -1.

The solution is as follows:


  from collections import defaultdict
  from heapq import heappush, heappop

  class Solution:
      def findCheapestPrice(
          self, n: int, flights: List[List[int]], src: int, dst: int, k: int
      ) -> int:
          heap, edges, stops = (
              [(0, src, 0)],
              defaultdict(list),
              [float("inf") for _ in range(n)],
          )

          for u, v, w in flights:
              edges[u].append((v, w))

          while heap:
              curr_dist, u, stop = heappop(heap)

              if stop > stops[u] or stop > k + 1:
                  continue

              stops[u] = stop

              if u == dst:
                  return curr_dist

              for v, w in edges[u]:
                  heappush(heap, (curr_dist + w, v, stop + 1))

          return -1


_ Time Complexity:

  O(n + e * k * log(e * k)) - Where n is the number of nodes, e is the number of edges, and k is the
  maximum number of stops.

_ Space Complexity:

  O(n + e * k) - The stops array takes n space, and the heap will take e * k elements.