https://leetcode.com/problems/cheapest-flights-within-k-stops

There are a lot of different ways to handle this problem: using DFS, BFS, Dijkstra, Bellman-Ford, Dynamic programming. For me it is easier to use BFS, because we are asked to find the shortest distance between two given cities, not with all dst like in Dijkstra or Bellman-Ford.

BFS the idea is to traverse our graph in usual bfs routine and also take into account that we can have maximum k stops, that is our pathes should have length less or equal than k + 1. To implement bfs in python usual way is to use deque (double ended queue), it works pretty fast in python. We can not use usual list like in dfs (for similate stack), because here we need to pop elements from the beginning of our queue.

We need to keep in each cell of our queue 3 values: current city, current number of visited cities and current price. It is worth to investigate new city if 3 conditions met:

  1. Our current price is less or equal to minumum price found so far.
  2. If we still can visit one more city, visited < k+1.
  3. The current city is not our destination yet.

If we reached our city of destination, we update minimum price we get so far.

Complexity, both time and memory of bfs is O(V + E), where E is number of edges and V is number of vertices. Note however, that we have here multipass bfs, when we visit node, we do not mark it as visited, and we can visit it several times. In fact this algorighm is very similar to Dijkstra algorighm, and I think complexity is O(E + V^2) = E(V^2), because we traverse each edge only once, but we can visit nodes a lot of times. Update I do no think it is quite true, need to be checked.

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        graph = defaultdict(list)
        deque_vert = deque([[src, 0, 0]])
        min_price = float('inf')
     
        for i, j, w in flights: 
            graph[i].append([j, w])

        while deque_vert:
            city, visited, price = deque_vert.popleft()

            if price <= min_price and visited <= k and city != dst:
                for neibh, price_neibh in graph[city]:
                     deque_vert.append([neibh, visited + 1, price + price_neibh])
            
            if city == dst:
                min_price = min(min_price, price)
                
        return min_price if min_price != float('inf') else -1

Dijkstra

There is better complexity time solution (however we need bigger tests to check it). I was wonderig is it possible to use SortedList, instead of Heap in Dijkstra algorighm, and the answer is yes! What we need to do is to pop the smallest element and to insert into our list in logarighmic time. Here we need to keep 2-dimensional table dist for shortest distances with given length of path.

Complexity I think it is O(E+(Vk)*log(Vk)), because there will be no more than Vk different elements in our SortedList (Heap) at any moment.

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        graph = defaultdict(list)
        dist = [[float("inf")] * (k+2) for _ in range(n)] 
        dist[src][0] = 0

        SList = SortedList([[0, 0, src]])
        
        for i, j, w in flights: 
            graph[i].append([j, w])
        
        while SList:
            price, visited, city = SList.pop(0)

            if city == dst: return price
            
            if visited <= k:
                for neibh, price_neibh in graph[city]: 
                    candidate = dist[city][visited] + price_neibh
                    if candidate <= dist[neibh][visited + 1]:
                        dist[neibh][visited + 1] = candidate
                        SList.add([price + price_neibh, visited + 1, neibh])
                        
        return -1

Solution 3

We can use state dp[i][j] where i is node and j is number of fligths made.

Complexity

Time and space complexity is O(E*k).

Code

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, K):
        dp = [[float('inf')] * n for j in range(K + 2)]
        
        for i in range(K + 2): dp[i][src] = 0
        
        for i in range(K + 1):
            for u, v, w in flights:
                if dp[i][u] != float('inf'):
                    dp[i+1][v] = min(dp[i+1][v], dp[i][u] + w)
        
        return dp[-1][dst] if dp[-1][dst] != float('inf') else -1

If you like the solution, you can upvote it on leetcode discussion section: Problem 0787