Bellman-Ford - Cheapest Flights within K Stops - Leetcode 787 - Python 

💡 GRAPH PLAYLIST: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-EgI5nU9etnU.html

Hey neetcode! Today I got intern offer from one of the FAANG companies. All credits to you for introducing me leetcode and easy python solutions. That really helped me in interviews. Thank you so much.

I think my study plan is to go through your list of videos and see which problems scare me, and tick them off one by one. because it's so relaxing to know that you have a solution.

There's no way in hell I would've been able to solve this in an interview. I think it's LC hard. Not only it's an advanced graph algorithm but also it's a variation of bellman ford.

This is the first time I did not understand something you taught @NeetCode

Your solution is constantly the most readable and elegant one! Really appreciate all your efforts!

Thanks for the explanation man! You pointed out what each of the prices and temp array means and made the algorithm very intuitive

This channel is so underrated, NeetCode fr the GOAT

I loved your videos, pls continue posting more topics. I love the way you teach.

Awesome explanation. For my understanding it was easier when I named "prices" "prevStepPrices" and "tempPrices" "currentStepPrices", that way it's clear why we're using a temp variable.

Thank you, I have an interview for a MAANG company next week and I feel confident with the help of your videos!

i really like the use of temp array to limit to k stops ,regular BF doesnt take care of that

Explanation for 'k+1' : if k stops are allowed , then only vertices that are of use are 'k' + 'src' + 'dst' == k+2 , therefore maximum routes to dst can be (k+2)-1.

Mind Blowing approach, Thanks Man

Thanks for the neat explanation and code!

superb explanation..specially the temporary array part,thanks a lot!!!

Phenomenal explanation. Thank you so much !!!

One easy way to make it more efficient is to check if there is an improvement between iterations, and break out of the loop if there isn't. So replacing line 14 for: if prices != tmpPrices: prices = tmpPrices else: break

Do let me know if I am correct here. The explanation is that Bellman Ford converges with |V|-1 tries because it gets to traverse all the routes including the route that has |V|-2 vertices between vertices at two extremes is the graph. So, with K vertices in between, we run K+1 passes.

Great explanation, Thank you so much !❤

Dijkstra is normally pronounced Dyke-struh, in IPA /ˈdɑɪkstɹə/. It is a Dutch name, where the 'j' is always silent or pronounced like a 'y'. So the name should be 'dyk (bike, hike in English) -stra'.

Just a technicality, but isn't this approach O(k*(V+E)), since we are copying the temp_cost array at each iteration?

Thanks for the vid 👌

You are just tooo tooo good thankyou!

Since there are no negative weights I chose to use Djikstras algorithm. It was nice seeing this solution too!

Thanks for another great video!! Idk why but I somehow find the general DFS solution easier to understand & implement. The DFS solution is like any other graph search problem, but yes it's much bulkier than this algorithm.

Great video!

Does it also mean this code should work for a scenario with at least K stops and can you specify a recursion for this?

We could still use the Dijkstra algorithm. The core idea is to use an array to keep updating the minimum steps(also minimum cost by using the minheap) to reach certain nodes until we reach the dst node. Here is the C++ solution: int findCheapestPrice(int n, vector& flights, int src, int dst, int k) { // build adj lists; unordered_map adjs; for (auto i: flights) { adjs[i[0]].push_back({i[1], i[2]}); } // record ver vector vertex2Stops(n, INT_MAX); k += 1; priority_queue pq; // starts from src with 0 cost // {cost, nodeid, stops}; pq.push({0, src, 0}); while (!pq.empty()) { auto t = pq.top(); // std::cout

Does anyone know why we use the `tmp` array? Other implementations of Bellman-Ford online don't use it.

This is a very simple example, you could have picked one with cycles... Also the time complexity would be O ( k * (V+E) ) . The extra V is due to the copy of temp.

Such a clean explanation! Loved it

What device do you use for recoding these videos? The visuals are very helpful.

Very good explanation

quick question -- at 11:30 to 11:50 when evaluating whether the price of B should be updated, would it make more sense in your drawing to look at B's price in the temp table, since in more complex graphs there could be multiple potential updates to B when looking at the next 'layer' of BFS and we want to ensure we're saving the minimum price?

Great explanation. I did it in a DFS way but don't know why it doesn't work. Maybe I'm missing some edge cases.

Amazing!!!

simply awsome

Hi Neet! Very nice solution you have there! I tried to DP this problem but got a timeout and I don't know how to add cache to it ! Can you help me with it ! Thanks a lot!

Thank you so much

How did you come up with this solution ? is there any resource ? it's simple , i agree the most

Thanks Kevin😀

This solution looks a lot like a 2D dynamic programming bottom-up approach, with the additional optimization in memory (because you only need the current and the previous value of k). I think this view of the problem might help others to understand it more easily, bc we can ignore all the relationship with bellmanford algo.

Do we really need the continue block? Assume if prices[s] is infinity, its anyway not going to be less than tmpPrices[d] even when its value is infinity.

Hm. I just copied your code, and then changed k=0 for the inputs, which should give -1 but instead gives 500. Help?

Since the the graph does not contain negative weights, cant we use Dijkstra instead ?

Great Video!!! I wanted to know, which kind of algorithm method is this? Is this DP? I am new to graphs and competitive coding in general, please do let me know, thanks!

Great solution but I love how you misspell Dijkstra into Djikstra in all your videos lmao

Instead of quoting bellman ford right away, I would use dynamic programming. We would store a table which will be V by (k+1). For the 0th stop, we would only explore the neighbors to the source. For the 1st stop, we would look at all the vertices that have been explored and try to check if the distance their plus the distance to neighbors would improve the current distances. We would only take the last row as the final solution. However, to save space, we could only keep two arrays of length V at a time. I was hoping this solution could be a good way for people who haven’t looked at Bellman ford’s algorithm. However, this would need an adjacency list that is easily searchable which adds extra machinery.

thank you

For those that are confused, I suggest watching other videos that explain Bellman-Ford in isolation. The explanation in this video is not clear at all.

If you were to use pure Djikstra, how would you handlel the k stops condition?

is there a way to solve this without using the temporary distances array? how come traditional bellman-ford doesn't include this?

``` for i in range(k) -> temp = prices.copy() for s, d, p in flights -> temp[d] = min(price[s] + p, price[d]) prices = temp return temp[dst] ``` I think we dont need to check if price[s] is infinity or not,

Why Multi Source BFS wont work for this problem. Coded it, but is failing 43rd testcase. Can anyone know what it is failing ? Attached code for reference: class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: graph = {} for c1, c2, p in flights: if c1 not in graph: graph[c1] = [(c2, p)] else: graph[c1].append((c2, p)) for i in range(n): if i not in graph: graph[i] = [] res = float('inf') queue = deque() queue.append((src, 0)) visited = {src,} while queue: if k == -1: if res == float('inf'): return -1 return res queueLen = len(queue) while queueLen: city, price = queue.popleft() for nextC, nextP in graph[city]: if nextC in visited: continue if nextC != dst: queue.append((nextC, price + nextP)) visited.add(nextC) else: res = min(res, price + nextP) queueLen -= 1 k -= 1 return -1 if res == float('inf') else res

Can someone explain why only (k+1) iterations done for this problem?

hope one day i reach your level♥

brilliant.

Like always, click the like button before I watch it.

Sorry, I still don't understand why we need the temp copy. Why 743. Network Delay Time don't need a copy ? Can anyone explain more.

This question can also be resolved by SPFA algorithm. The theory is similar here, but much faster than Bellman-Ford .

I'm new to English and algorithm. And now I'm confused, is it dikestruh or jikestruh?

Unfortunately, I just don’t understand how applying the Bellman Ford algorithm, magically solves the problem. If there’s someone who can explain why it works, it’d be very helpful.

i want to know other questions about negative price

Hi @Neetcode, why don't we need DIjkstra's algorithm for this problem?

This code fails in leetcode due to the if condition leading to continue, here is a working implementation of above explanation class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: price = [float('inf')]*n price[src]=0 for i in range(k+1): temp = price.copy() for s,d,p in flights: temp[d] = min(temp[d],price[s]+p) price = temp if(price[dst]==float('inf')): return -1 return price[dst]

Why do you need tmpPrices?

One small question, when we are assigning prices = tmpPrices aren't the two lists actually referencing to the same data? In this way if we make any change in tmpPrices down the line inside the loop then the same will be reflected in the original array right? Doesn't this defeat the whole purpose of using a tmpPrices array?

Nice🎉

Neetcode is OP

I tried to solve this with a modified Dijkstra algorithm which gives infinite weight after number of hops is > k+1. Well it kinda works for most of the cases but some inputs breaks doesn't produce the smallest path, as expected for some problem that can be solved only by DP and you try a greedy approach. Life sucks. I'm avoiding DP since it's a hard topic and I'm not even good in other topics, so I'm saving this question for later.

Isn’t djikstra pronounced with a hard I like “eye”?

1. It's not a true Bellman Ford, but a modification that supports the max k requirement. Here is a nice explanation of true Bellman Ford: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-obWXjtg0L64.html 2. The question can be solved with a modified BFS, which stops after k + 1 iterations and does not limit visits to a node, but does that only if it can be done more cheaply than prior visits This solution is faster than the BF solution on Leetcode: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: k += 1 # k is stops, we count legs adj = collections.defaultdict(list) for s, d, c in flights: adj[s].append((d, c)) totalCost = [math.inf] * n changes = True queue = deque([(src, 0)]) i = -1 # reaching src is not an iteration while queue and i < k: print("Iteration", i) i += 1 for j in range(len(queue)): node, cost = queue.popleft(); if cost >= totalCost[node]: print("Reached", node, "again at a higher cost", cost, "ignoring") continue print("Reached", node, "cost", cost) totalCost[node] = cost for dest, price in adj.get(node, []): newCost = cost + price if newCost < totalCost[dest]: queue.append((dest, newCost)) result = totalCost[dst] return result if result != math.inf else -1

good vid, just one thing you can improve on I may suggest is don't put other RU-vidrs to shame by making such good content

Its just too much man, How many problems are out there, and why should I learn all this, Fuck it man

Here is the main idea in copy array, because in every iteration of k, we dont stop

Nice trick !! One question though. Using temp array is kind of deviation from Bellman Ford's right ? If it were regular Bellman Ford, and k = 0, even a single iteration would also give: 0 0 1 100 2 200 But our condition produces: 0 0 1 100 2 500

tbh solution didn't make sense.It says bellman ford but talks about BFS throughout video. Also doesn't clearly explains the intution.

why we use temp array can u explain agian??

With the help of this solution I made the BFS solution: class Solution: def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int: adj = {i:[] for i in range(n)} deq = deque([(0,src)]) prices = [float('inf')] * n prices[src] = 0 for cur, to, price in flights: adj[cur].append((price,to)) for i in range(k+1): for j in range(len(deq)): cost, node = deq.popleft() for price, to in adj[node]: new_cost = cost+price if prices[to] > new_cost: prices[to] = new_cost deq.append((new_cost,to)) return prices[dst] if prices[dst] != float('inf') else -1

Do we need to consider the edge case where a direct flight between two nodes is cheaper than intermediate nodes?

Temp array isn’t still clear. You rushed it too quickly.

it's my BFS solution. a little complicated.... var findCheapestPrice = function(n, flights, src, dst, k) { let graph = {}; for(let i = 0; i < n; i++) { graph[i] = []; } for(let [from ,to, price] of flights) { graph[from].push([to, price]); } let que = [[src, 0]]; let minPrice = Infinity; let visited = {}; while(que.length && k >= 0) { let len = que.length; for(let i =0; i < len; i++) { let [currNode, currPrice] = que.shift(); for(let [nextNode, nextPrice] of graph[currNode]) { let newPrice = currPrice + nextPrice; if (newPrice < ( visited[nextNode] || Infinity)) { visited[nextNode] = newPrice; if (nextNode === dst) { minPrice = Math.min(minPrice, newPrice); } else { que.push([nextNode, newPrice]) } } } } k--; } return minPrice === Infinity ? -1 : minPrice; };

I did it another way an encountered Time Exceeded :( so came here to watch this.

> 1:54 Djikstra