Cheapest Flights Within K Stops
By Owen Wu
Summary
## Key takeaways - **Bellman-Ford for Cheapest Flights**: The 'Cheapest Flights Within K Stops' problem can be solved using the Bellman-Ford algorithm, which iteratively updates shortest path distances. [00:28] - **Iterative Price Updates**: The algorithm maintains a temporary array to store updated prices, ensuring that updates within an iteration do not affect the current iteration's calculations. [01:08] - **K Iterations for K Stops**: The core logic involves running the relaxation process K times, corresponding to the maximum number of stops allowed in the flight path. [01:50] - **Handling Unreachable Destinations**: If the destination's price remains at infinity after all iterations, it signifies that the destination is unreachable, and -1 is returned. [02:04] - **Algorithm Difficulty Acknowledged**: The speaker admits to not being able to solve this LeetCode problem independently, even after a year, highlighting its challenging nature. [00:11]
Topics Covered
- Bellman-Ford is not BFS for cheapest flights.
- Why Bellman-Ford requires temporary price storage.
- Understanding the Bellman-Ford destination variable.
- Bellman-Ford's iterative nature for K stops.
- Handling unreachable destinations in Bellman-Ford.
Full Transcript
Hello everyone, welcome back to my
channel. Today, let's go over a famous
grind 75 medium question. And
unfortunately, I was not able to resolve
this question on my own after learning
it over a year ago. So, I am just stuck
on exactly where to start. So yeah,
instead of spending a bunch of time
coming up with a sub-optimal solution,
I'll just restudy the question, restudy
the solution from necode, which is
Bellman Ford's algorithm. So cheapest
flights within K stops. It looks like a
BFS solution where we are going to push
to a que and then pop from the queue.
Well, actually, I don't really
understand how this works because I
didn't come up with this solution. So it
looks like dystersman
Ford.
So you have n flights and I guess we're
going to set the source to zero. So
that's a common pattern bellman Ford or
dystra any kind of the shortest path
algorithm. So for K plus one tmp is
prices.copy.
I guess we don't want to modify the set
while it's being or the list while we're
updating it in flights. So
if price is S is equal to infinity
then continue
otherwise
if price is S
plus P is less than D then
TMP of D is price is S plus P. So what
is D exactly? It's TMP of D.
I guess that's the destination.
And we're going to do this K times,
hence the loop here. And then TMP is
equal to prices or prices
is equal to TMP.
Okay. So if prices DST is equal to
infinity, I guess we just return
negative 1 because we couldn't even
reach the destination. Otherwise, return
prices
what is it? price is negative 1 or price
is DST
DST. Okay, so again I'm going to come
back to review this question later
because I was not able to resolve it on
my own and again this is neat code
solutions so credit to him and that's it
for this video.
Loading video analysis...