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

0:00 - Read the problem
3:55 - Drawing Explanation
15:28 - Coding Explanation

leetcode 787

#bellman #ford #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[jonaskhanwald]

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.

[kickradar]

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.

[chaitya]

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

[gaaligadu]

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.

[ancai]

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<vector<int>>& flights, int src, int dst, int k) {
// build adj lists;
unordered_map<int, vector<pair<int, int>>> adjs;
for (auto i: flights) {
adjs[i[0]].push_back({i[1], i[2]});
}

// record ver
vector<int> vertex2Stops(n, INT_MAX);
k += 1;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
// starts from src with 0 cost
// {cost, nodeid, stops};
pq.push({0, src, 0});

while (!pq.empty()) {
auto t = pq.top();
// std::cout << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << "\n";

pq.pop();
int cost = get<0>(t);
int nodeid = get<1>(t);
int stop = get<2>(t);

if (stop > k || stop > vertex2Stops[nodeid]) {
continue;
}
// keep updating the minimum steps to reach certain nodes.
vertex2Stops[nodeid] = stop;
// minimum steps to reach the dst node and minimum cost due to min heap.
if (nodeid == dst) {
return cost;
}

for (auto nei: adjs[nodeid]) {
// non-visited;
// if (!visited[nei.first]) {
auto temp = std::make_tuple(nei.second + cost, nei.first, stop + 1);
pq.push(temp);
// }
}
}

return -1;

[GoogleAccount-wyhc]

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.

[rameshjha]

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.

[rahulpandey]

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

[nashifcod]

This channel is so underrated, NeetCode fr the GOAT

[kritidiptoghosh]

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

[supermario]

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

[CostaKazistov]

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'.

[marcelofernandes]

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

[willy]

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

[somdutroy]

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.

[RandomShowerThoughts]

So I was able to modify Djisktra's algorithm, there were a couple of things that i had to do in order to get this to work:
1. PQ based on steps (nodes inbetween)
2. Allow reconsidering of visited nodes, so that we can update the values if and only if, the weights were smaller

[therealjulian]

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.

[soumyajitganguly]

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.

[guambomber]

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

[anthonyleong]

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.