Cheapest Flights Within K Stops

3 min read
Graph
LC-Medium

Oct 21, 2022

3 years ago

LeetCode

Solution

Use the Bellman-Ford Algorithm
Dijkstra's Shortest Path Algorithm won't be efficient here because of the "within k stops" restriction.
Kinda like Breadth-first Search, but instead you look at all edges in each iteration.
Honestly just watch the Neetcode video, he does a really good explanation, but basically, at each point in time, i.e. for k + 1 iterations:
- Look at all edges, and update distances. Initially, all distances to node except to source are infinite. Distance to source is 0.
- Then, initially, all edges that are reachable from our source would be updated, with their weights that are attached to 0.
- Every other node that is not currently attached to the source, would not be looked at in the current iteration, but in subsequent ones.
  - If this is the case, why do we look at all edges, even if they aren't currently reachable?
    - Well first, it makes the code much more simpler.
    - But the actual reason is the fact that we might find a new path with a shorter cost after we first initially find a path to that node
    - To ensure we have the best answer, we need to look at all the edges in each iteration
    - We do k + 1 iterations because if there are 3 nodes in our path, we made only 1 stop. That's just how the math works.
We use a temporary array to update the prices because if we update the original prices array, our intermediate calculations would affect the actual answer, i.e. take the following example:
We would initially update cost to go to B from A as 100.
Now when we look at the edge connecting B to C, we would incorrectly calculate the distance as 100 + 100 = 200. We have not even reached B yet, we're still in the middle of processing it. So we cannot update the cost for C just yet.
Also, why is this line if prices[s] + p < temp_prices[d]: using temp_prices instead of prices??
- Because we might have already gotten a new temp price in our current for loop that we should use instead of using the global prices array.
  - This is what NeetCode said. I have no clue what that means lmao.

Time	Space	Explanation
`O(E * k)`	`O(E)`	Algorithm runs k times for each edge

def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: prices = [math.inf] * n prices[src] = 0 for _ in range(k + 1): temp_prices = prices[:] for s, d, p in flights: if prices[s] == math.inf: continue if prices[s] + p < temp_prices[d]: temp_prices[d] = prices[s] + p prices = temp_prices return -1 if prices[dst] == math.inf else prices[dst]