Cheapest Flights Within K Stops | DFS + Pruning | Leetcode
Vložit
- čas přidán 13. 06. 2020
- This video explains a very important graph programming interview problem which is to find the minimum cost path from source to destination.This is a very typical shortest path problem and can be solved by using a variety of algorithms like Dijkstra, Floyd Warshall, Bellman Ford, BFS, DFS with memoization or pruning.In this question, we are allowed to have a maximum of K number of stops from source to destination.This is the only additional constraint.I have shown the simplest approach to solve this problem which is by using DFS + Pruning.I have first explained the intuition and then i have shown the working of the algorithm by taking an example.At the end of the video,i have also shown the code walk through. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
SIMILAR PROBLEMs:-
DFS: • Depth first search | D...
BFS: • Breadth first search |...
![Cheapest Flights Within K Stops | Graph | [CODE + Explaination] | Amazon | GFG 🔥](http://i.ytimg.com/vi/YmnwiYKe6g8/mqdefault.jpg)
How this solution is going to take just O(n + e) time even in the worst case? Can you explain?
I forgot to mention that time depends on your sparsity of graph. For dense graph, for finding just 1 path, time is O(V+E) but for sparse graph you can find all paths in the same amortized time. For dense graph, for finding all possible paths, you will have O(V.(V+E)) which can go to V^3 because E=V^2 for dense graph. So, the time for this problem will range from O(N+E) to O(N.(N+E)). This totally got out of mind while explaining. Thanks for this question :)
@@techdose4u what if we have a complete graph in which all paths from src to dest is at most k stops away, thus DFS is not going to prune on (k < -1), as this condition, would never hit and DFS is also not going to prune on condition (currPrice > minFare) as somehow say, we are getting the minFare cost in decreasing order, thus we are actually going to every single path from src to dst?
It can't have all paths in decreasing order in a dense graph. Now pruning depends on when you find a path with lower cost. If graph has a special configuration so that your DFS algo (depending on how you made adjacency list) do not prune, then this can only happen when all paths leading to dst are within K stops and all the paths in our DFS are coming in decreasing order of totCost. But this test case will be rare. Also, I mentioned before explaining that this is one of the slowest method (even though it's VE but still it's recursion and not loop).The only optimization is pruning. This works fine if the test case is not designed to make this technique fail. If time complexity is more stringent then try other optimal methods using dynamic programming.
@@techdose4u Got it. Thanks!
👍
I am having TechDose regularly as suggested by my frnd and its really making me more efficient coder.
Nice :)
He sets visited[src] = true so that while exploring some node, you don't visit it again. That can happen if there exist cycle in the graph. But setting it again to false after for loop so that that node can be visited in some other path as he explained in some reply.
Actually here you can even avoid usage of visited array. Not using visited array in dfs will give you all different paths from source node to any other node. ALL DISTINCT PATH!! As you are pruning here by two constraints that are 1- k(at most k stops) and 2- smaller cost. You will get all the paths that are in bound of these two constraints. And we want one of them that is having smallest cost.
Hope it helps. @TECH DOSE please correct me if I am wrong anywhere.
Keep it up!! TECH DOSE, you are helping a lot of people!
Good work, We want more solution like this: Simple Method+ Pruning , I Learned a New things ,Thank you
Keep learning :)
Thanks for teaching a new concept Pruning with dfs.
Thanks for the very clear explanation and listing all the possible ways to do it.
For the DFS + Prunning method, even if we are using a visited array, how is the time complexity still the worst among all other techniques?
How can the time complexity id O(n+e) , you are trying all possible paths with pruning optimization and we are visiting the same vertex again in some different path?it seems time complexity will be more than O(n+e)
I solved it using BFS with the help of heap. Really interesting problem. Thanks for the alternate solution using dfs!
Can tell me the full algorithm technique?
Did you store the cost of every possible s to d path within 'k' stops in a min-heap and then just returned the 1st element/root of the heap???
Always makes problem more simple and solve with efficient solution ! Good work :p
Thanks :)
@@techdose4u bro .pb is not working
@@techdose4u why you have used that by the way
If DFS explores the longer path first, then pruning will not help. So it should be BFS + pruning as we will encounter the shorter path to destination and later when we explore the longer path, we can use pruning. Can someone please explain???
Why does Cost matrix in the code you have provided has the dimensions (n+1,n+1) and not (n,n)?
TECH DOSE, please make a video on other ways of doing this problem, will help a lot!! Also in many interviews they ask to solve the same problem but with different approaches.
Yea right.
why did you take the cost matrix size n+1?
Bro, Do you mouse to write on the black board ?? if any specific app can you tell so that I can use that to explain in my interviews ?
Thank you sir!!
Awesome explanation...thnx a lot.
Waiting for this!!!!
Solved it?
@@techdose4u Not yet!
thank you sir for so awesome content.i just want to make one request to you that please try to make solution videos using other approaches also like dijkstra algo etc.This will help our mind to evolve and we can think of many solutions to a problem whenever interviewer asks us tell approach to solve the questions.once again thank you for doing so much hard work for all of us.
Yea sure...I am trying to do this.
thank you very much sir awesome content ! i actually wanted to see dijkstra's algo approach as well.. if you have some time please make this solution based on dijkstra algo as well.. ❤❤❤
Yea sure. I will explain graph as well :)
Why are you using this line of code ?
if prices[s] == float("inf"): continue
is it necessary since you initialize prices[src] = 0 in the begin so in my understanding it can't be infinite again
Iam getting TLE with the above mentioned approach
Try to optimize with priority queue code
Great explanation!! But did you use prunning in your code.. Like when (totalcost>fare) return;?
Yes. Inside the for loop in solve, I have checked for totCost > fare.
Are we trying to explore every possible path in this solution and making optimization by not making further calls in case the number of stops surpasses k or cost of current path becomes more than minCost .
HI Tech dose i guess pruning will not work with negative weight
if we are returning from a particular node just because of value is greater then total max and on next node there is negative value then pruning will fail.
Not only with this problem but in general graph where positive and negative value present.
awesome solution !! btw what software do you use to draw on the screen? can you please share the name
The same method I came up with in C#. In large test cases TLE comes.
How we can solve this using Dijkstra with the constraint of 'K' stops. It's a greedy method, will it work here ? If there is no constraint for 'K' stops, then it would work for sure!
A small optimization which we can make in the given code acc to me. I think on line 16 we can replace
why we are taking visited array ?
suppose if src=0 ,dst =3
1 path -> 0->1->2->3 and suppose 1->2 cost is 500 and u made 2 visited
2 path -> 0->2->3 and suppose 0->2 cost is 100 but u made 2 visited so we cant go there but it will be minimum cost path
Please explain?
Please make video on graph with some questions
This approach is giving TLE
Optimize by using heap
Hi,
The same question can be solved using Bellman Ford or dijkstra algorithm, If possible please update on the same, or create a new video, As I was checking some other solution and these two seems to be efficient than dfs.
Not sure though but Bellman Ford uses concept of dp also.
Grt explanation. I solved it using the same way. I know dijikstras but how can we do it when there is parameter k using dijikstras algorithm
Can anyone post java code with same prototype/algorithm
Content is very useful, I appreciated! WARNING RUBBISH ADS: { Actually I got some ads like: " In order to take my girlfriend on dinner so I started " , bhai etna bhauk kyo ho rha toda sabar kar le dimag mat kharab kar.}
great
You explained very clearly,by the way i follow you channel,you really explain things very clearly,even the tough questions.But your solution is getiing tle on leetcode for this problem.
Use priority queue in implementation
can u please explain this question using dijkstra's algo.
sir how to do this question using dijkstra since there is a constraint of k?
Dint try it yet. But you cannot solve it using MST algos.
Nice video but you said that the time complexity of your algorithm is O(V+E) but I think it is O(V^V). Could you please explain or correct me if I am wrong?
Please read the pinned comment.
very nice!
Thanks
I think the test cases for this problem were not very exhaustive. You can see accepted answer in python and I think it does not even implement several optimizations and checks for test cases but it still passed.
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
answer = 10**9
from_city = {}
for source, destination, price in flights:
if source in from_city:
from_city[source][destination] = price
else:
from_city[source] = {destination: price}
stack = [(src,0, K)]
while stack:
start, cost, steps = stack.pop()
if start!=dst:
steps-=1
else:
answer = min(answer,cost)
pass
if steps>-2 and answer>cost and start in from_city:
for destination in from_city[start]:
price = from_city[start][destination]
stack = [(destination, cost+price, steps)]+stack
return answer if answer!=10**9 else -1
Yes I think that too. But just enjoy the accepted code for now :P
Can I use this solution in interviews??
great explananation
Thanks :)
Nice explanation , but this solutions give TLE on leetcode. Only bellman ford shall pass on leetcode
Optimize the code
This method is giving TLE in leetcode
Awesome explanation. Bdw rap starts at 18:19. Thank me later :D
😅
hahahaha
please make a video on operations on vector of vector (especially for comparators for vector of vector)
👍
Sir, can't we apply union find kruskal algo for min weight path
That can also work because finding minimum cost spanning tree will also lead to min cost path. But they should be in the same component. I guess that's why you want to use union find.
Yes, but I thought of it and I think kruskal won't work coz the spanning tree could be from the left subtree of source to the right or any other subtree of the source, that ain't the path from source to destination we want
I thought about it and concluded that MST algos won't work because of K stop condition 😅
Yeah, me too, actually I didn't even see the problem and I committed about MST but then I knew the problem
thanks
Welcome
Why is dfs with pruning less efficient than BFS?
Not less efficient. If you use BFS in combination with other DS then BFS will be more efficient.
Do You use backtracking in your DFS? That is really a Smart thinking.
Ahh, awesome trick. I was trying to implement dfs with memoization for a long time and felt going in wrong direction unless saw your trick. Can u help me with memoization approach as well? Thanks in advance.
Paste your code in comment or share the gist link. You can get help.
@@techdose4u
Here is the code.. Its getting TLE
class Solution {
int INF = 0x3F3F3F3F;
Map memo = new HashMap();
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
Map[] graph = new HashMap[n];
for(int i = 0; i < n; i++)
graph[i] = new HashMap();
for(int[] f : flights) {
graph[f[0]].put(f[1], f[2]);
}
int ans = findMinimumCostPath(graph, src, dst, -1, K);
return ans == INF ? -1 : ans;
}
int findMinimumCostPath(Map[] graph,
int src, int dst, int stop, int maxStop){
if(src == dst)
return 0;
int minCost = INF;
String key = src + "-" + dst;
for(Map.Entry entry : graph[src].entrySet()){
if(stop < maxStop)
minCost = Math.min(minCost, entry.getValue() +
findMinimumCostPath(graph, entry.getKey(), dst, stop + 1, maxStop));
}
memo.put(key, minCost);
return memo.get(key);
}
}
@@siddharthkumar2761 Were u able to get memoization working ?
With DFS+pruning but without memoization it runs into TLE
Nicely explained thanks, can u please tell me , why did u write this : visited [src]=false at the end??
This is just the same concept for cycle finding algo in graph. First mark a node visited and then explore. While returning back from the node, mark it as unvisited so that it can be explored in some other path as well.
He sets visited[src] = true so that while exploring some node, you don't visit it again. That can happen if there exist cycle in the graph. But setting it again to false after for loop so that that node can be visited in some other path as he explained.
Actually here you can even avoid usage of visited array. Not using visited array in dfs will give you all different paths from source node to any other node. ALL DISTINCT PATH!! As you are pruning here by two constraints that are 1- k(at most k stops) and 2- smaller cost. You will get all the paths that are in bound of these two constraints. And we want one of them that is having smallest cost.
Hope it helps. @TECH DOSE please correct me if I am wrong anywhere.
Keep it up!! TECH DOSE, you are helping a lot of people!
please tell me algorithms which are important to master graphs
Please follow my graph playlist. I am making the important algos only.
@@techdose4u yes i am following this playlist & thank you for these awesome videos.i love the way you explain.
Can we find shortest path in a weighted graph with this approach?
The graph you saw is weighted. Recursion is always slower as compared to loops even for same number of observable operations. So go with Dijkstra. But DFS will always work but it won't be efficient.
yes we can but its too costly , Use djikstras or bellman ford to reduce the tc
@TECHDOSE Great Video Sir, can u please explain why are we making vis[src]=false; again after the recursive calls.
Thanks in advance :).
We dont want to fall in a loop. So whenever we are processing a node, we don't want to travel to that node again while finding mincost from src to day and so we keep making each node true. Now as we return in our recursion, we will have to make it false so that the node can get included in some other path. This is just like cycle finding algorithm, where we make a node true and enter and while returning we make it false.
@@techdose4u got it thanks
I got TLE when I recently tried.
me too
I think leetcode expect us to solve using DP
Cost(1,2) = 200? In the question, it is not 100?
Sir this solution is giving tle .please check it
Bro please explain all the 6 approach you've listed
I will explain all in future but explaining them without a reference video is not possible now.
@@techdose4u sure bro... Thanks
47 / 49 test cases passed. if I use DFS + Pruning.
Optimize the code as per new TCs
Why this seems so similar to travelling salesman problem without this pruning? Or is it only me ?
47/49 test cases passed in leetcode using DFS approach. But I know the intension of the vedio was to learn DFS + pruning.
New TCs added. Please optimize the code
@@techdose4u i dont think any optimisation left in this approach,if u know pls tell us how to make it work for last few test cases on leetcode. it's failing in last 4 TCs .
Time Limit Exceeded in case of n = 100,
I'm getting TLE in leetcode for this approach! :(
Same
For n=100
Thanks for solution
Pls also add solution using djikstra as i feel djikstra wont work here.
I haven't tried Dijkstra. May be we need to modify something there.
class Solution {
public:
void solve(int n,vectoradj[],int k,int src,int dst, vector&vis,int &ans,int cost){
if(k
Code Link : techdose.co.in/cheapest-flights-within-k-stops-dfs-pruning-leetcode-787/
Hello sir based on the problem's explanation I have got a hunch about solving this problem using knapsack. Correct me if I am wrong
No not knapsack. Just single source shortest path.
@@techdose4u ok thank you
👍
Sir this code is giving TLE
Please optimize the code with priority queue. I have written the bruteforce approach
This solution is getting TLE
Test cases are updated. Do some optimization on my code :)
it is giving TLE in leetcode .
can you make a video on memoization ?
question link dala karo bhai.
You can search using leetcode number. Name is also mentioned :)
its giving me TLE on 49th testcase out of 51
done it with same approach giving TLE on test 37.
Here is my code :
class Solution {
void solve(vector adj, int src ,int dst, int k,int &fare,int totalCost,vector vis){
if (k
In the code pass the adjacency list and the visited array by refernce , that is being copied a lot of times and thus giving tle
sir, pls write the code in JAVA also..
This solution is giving tle :(
Please optimize using heap for dijkstra
The solution not passing leet code tests and giving TLE. Please own what you publish on you tube.
Dijkstra won't work! u won't be able to store in the way the question asks!
Although you have explained the pruning method still you have not used that in the code. Your solution is good but not optimized.
Not passing on Leetcode