Score GATE AIR 301 , DAA university topper, Acknowledgement goes to Mr.Tushar Roy. Thank you so much sir. You made Data Structure And Design And Analysis Of Algorithm so easy
Excellent work sir: After all these days, I really found that implementing graphs through programming is very easy....you made it so clear. Thank you :-)
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
Compared to other 4-5 mins videos which also try to explain this algorithm. This video is longer than those but explains it far more clear than all other videos. GREAT WORK!!!
IT would have been nice if we followed the same suit as the Dijkstra and made the labels as A, B, C instead of 0,1, 2 here.. Given that distance is also numbers, it is a little confusing.. Great algorithm videos.. Thanks
Another excellent tutorial. Still looking forward to deeper explanation of Suffix Tries, specially Ukkonen's and probably Suffix Automata. I would be glad to hear about Dinic's max flow too. Great again! :)
The ith (1 indexed) iteration computes shortest distance with atmost i edges in between source vertex and any other vertex. That is why i runs from 1 to V-1. The V-1 th iteration will consider the shortest distance from source vertex to the any other vertex, with atmost V-1 edges in between.
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
How to understand the last iteration helps us find negative cycle in graph - Think like this, assume graph is V = 10 vertices. If a negative cycle exists, it must contains vertices this means you will go through the negative cycle AT LEAST ONCE. What does this mean ? This means the negative cycle will cause a change somewhere before the V-1 iterations or in the V-1 th iteration ( if entire graph is negative cycle ) Hence the final iteration uses the idea that somewhere earlier in the V-1 iterations , one of the calculations for shortest path became INCORRECT. Hence the vertex that got updated by the negative cycke , will keep propagating this "disruption" in every further relaxation of all its neighbours in all subsequent iterations. This means that if you were to carry out more than V iterations , all subsequent iterations would have a change somewhere due to this propagation.
Dear, from my understanding, it wont make any differnce, if order of edges taken as different at 13:10 minute of video explaing resson of vV1 times of algorithm. It would take V-1 times to run algorithm, because to get the shortest path in this particular example, all 3 edges(V-1) are involved. It can be appreciated from the algo, only atmost N edges can be added to the path after running the algorithm N times. Kindly correct, if I am wrong.
sir that was a nice video for understanding the concept...But the graph that you used initially did change after some time before u applied the first iteration plzz check....
sir u said that to reach 1 to zero the shortest path is 4,but sir if we move from 0 to 2 it will take 5 and from 2 to 1 it takes -3 so 5+(-3)=2 and this is the shortest path to reach from 1 to 0.
This video is really helpful.. I want to add a point here. When we are iterating v-1 times, can we break off in the middle when there is no update in the distance map (in a specific iteration just like best case of bubble sort)? I think without a single update we iterate through the same values and won't get a better distance until the end. Correct me if m wrong
It's a good explanation. However, I've one question: in the code when you do : `distance.get(u) + edge.getWeight()`, there can be integer overflow because `distance.get(u)` could return `INFINITY`. How does Java handle this? Also, there could be integer overflow even if `distance.get(u)` does not return `INFINITY`.. it is because `x + y`, in general, could overflow!
Thanks for your videos. I literally watched all your videos. Awesome work. I think, u can reach out to GeeksforGeeks and ask to link your videos there. Or, how about having your own website with all these videos. :) :)
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
Tushar that is a great flannel. I am concerned about the coffee stain near the left breast panel however. Please let me know if you were able to get it out with the washing machine. Anxiously awaiting your response. Also thank you for this video.
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
What if we take edges 0-2 and 0-1 before everyone else... you are bypassing the fact by considering those edges first whose both vertices are infinity. If 0-2 and 0-1 are taken first then in 1st iteration only other vertices are relaxed but it shouldn't be as shown in the textbook. Still confused how it's happening.
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
hi tushar roy. i just want to know whats the difference between these three algorithms: Bellman-Ford, Dijkstra, and Floyd-Warshall algorithms. Which algorithm is more accurate to solve the shortest path?
aries cruz Bellman and Floyd use dynamic programming whereas Dijkstra uses greedy strategy. The Bellman-Ford and Dijkstra's algorithm output a shortest path from an input vertex r to all other vertices reachable from r, whereas Floyd's algorithm generate shortest path between all pairs of vertices of the digraph. Also, Dijkstra works with weighted digraph with non negative edges. Bellman Ford works with digraphs with no negative cycles. Next you can talk about their differences on the basis of difference in time complexities.
Score GATE AIR 301 , DAA university topper, Acknowledgement goes to Mr.Tushar Roy. Thank you so much sir.
You made Data Structure And Design And Analysis Of Algorithm so easy
+Tushar Roy thank you so much again
Man, we really need to play your videos during lecture. Talk about fantastic instruction. Your channel is really my go-to source now
Your videos are the clearest tutorials I've found, and you cover so many different algorithms - thank you.
Excellent work sir: After all these days, I really found that implementing graphs through programming is very easy....you made it so clear. Thank you :-)
Really love your videos!Your enthusiasm and will to teach is pretty much evident through your videos.Thank you!
Shouldve watched this on valentines day. Gotta keep the distance between You and We small
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
Compared to other 4-5 mins videos which also try to explain this algorithm. This video is longer than those but explains it far more clear than all other videos. GREAT WORK!!!
You did the research instead of us and reduced our time. Thank you Tushar. Millions of hours reduced because of your research.
Have my daa exam day after tomorrow. This video helped me complete an imp topic in a span of 20 mins. Thank you!
Been looking around for exactly this kinda video for so long. Everything at one place, thanks mate!
excellent...ur approach of teaching is excellent. directly gets corelated to code implementation ( maps, parents etc.) thanks..
IT would have been nice if we followed the same suit as the Dijkstra and made the labels as A, B, C instead of 0,1, 2 here.. Given that distance is also numbers, it is a little confusing.. Great algorithm videos.. Thanks
waste fellow tushoraaaan yak thu he is convincing all intelligent people then wat abt less minded idiot videos
Another excellent tutorial.
Still looking forward to deeper explanation of Suffix Tries, specially Ukkonen's and probably Suffix Automata.
I would be glad to hear about Dinic's max flow too.
Great again! :)
Very helpful even after 7 years
I really like your simple teaching
Every video is a gem sir.
Thanks a lot. The most comprehensive lecture on belman ford :)
thanks for explaining cleary this algorithm. I had confusion regarding v-1 iterations thanks for clearing it.👍
The ith (1 indexed) iteration computes shortest distance with atmost i edges in between source vertex and any other vertex. That is why i runs from 1 to V-1. The V-1 th iteration will consider the shortest distance from source vertex to the any other vertex, with atmost V-1 edges in between.
Thank you! This video helps me to implement Bellman-Ford as generic class in Java.
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
Best algorithm lecture i've ever watched on youtube thankyou !
How to understand the last iteration helps us find negative cycle in graph -
Think like this, assume graph is V = 10 vertices.
If a negative cycle exists, it must contains vertices this means you will go through the negative cycle AT LEAST ONCE.
What does this mean ?
This means the negative cycle will cause a change somewhere before the V-1 iterations or in the V-1 th iteration ( if entire graph is negative cycle )
Hence the final iteration uses the idea that somewhere earlier in the V-1 iterations , one of the calculations for shortest path became INCORRECT.
Hence the vertex that got updated by the negative cycke , will keep propagating this "disruption" in every further relaxation of all its neighbours in all subsequent iterations.
This means that if you were to carry out more than V iterations , all subsequent iterations would have a change somewhere due to this propagation.
Dear, from my understanding, it wont make any differnce, if order of edges taken as different at 13:10 minute of video explaing resson of vV1 times of algorithm. It would take V-1 times to run algorithm, because to get the shortest path in this particular example, all 3 edges(V-1) are involved. It can be appreciated from the algo, only atmost N edges can be added to the path after running the algorithm N times.
Kindly correct, if I am wrong.
Space complexity should be O(E), not O(V). E>V. We need to store every edge to iterate through them.
You should use vertices name as a, b, c, etc and weights as 1, 2, 3 etc, using both numeric can confuse many people!
love you man, really like your teaching, thanks a lot, cheers
Best vedio for Bellmenford.....Thankuuu
U r great man...........Thanks a lot...Wish i could withdraw my college fees Give it to you...
sir that was a nice video for understanding the concept...But the graph that you used initially did change after some time before u applied the first iteration plzz check....
The if statement of your relax method and the method itself are missing closing brackets.
Anyways good explanation, keep up the good work!
excellent video ...enjoyed watchiing it
great explained......!!!!
sir u said that to reach 1 to zero the shortest path is 4,but sir if we move from 0 to 2 it will take 5 and from 2 to 1 it takes -3 so 5+(-3)=2 and this is the shortest path to reach from 1 to 0.
Very nice explanation! :) little suggestion, just improve video quality.
Good explanation. It was a little disorienting when you flipped the formula in iteration 2.
This video is really helpful.. I want to add a point here. When we are iterating v-1 times, can we break off in the middle when there is no update in the distance map (in a specific iteration just like best case of bubble sort)? I think without a single update we iterate through the same values and won't get a better distance until the end. Correct me if m wrong
u r correct, u can store changed vertices in a queue..
Excellent work Sir :)
very well explained. Thank you :)
Awesome !! can you please post Floyd Warshall too... Thanks in advance
+Tushar Roy Thank you so much :)
thnks sir... excellent explanation.. keep it up
How u have time to make these nice videos?..... @Apple developer :) Hats Off to ur Work...
It's a good explanation. However, I've one question: in the code when you do : `distance.get(u) + edge.getWeight()`, there can be integer overflow because `distance.get(u)` could return `INFINITY`. How does Java handle this? Also, there could be integer overflow even if `distance.get(u)` does not return `INFINITY`.. it is because `x + y`, in general, could overflow!
Thanks for the vedio Tushar. Really appreciate your effort. Could I ask for a link to the graph Class you create. Just need for my reference.
Thank u sir........🙏🙏
@Tushar Can you please explain why Dijkstra's algorithm does not work if there are negative weight edges?
Thank you. it was awesome :)
nice vedio .worth watching.👍
very helpful, thank you
Thanks for your videos. I literally watched all your videos. Awesome work. I think, u can reach out to GeeksforGeeks and ask to link your videos there.
Or, how about having your own website with all these videos. :) :)
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
Thank you
it was confusing at the beginning but I got it.
Tushar that is a great flannel. I am concerned about the coffee stain near the left breast panel however. Please let me know if you were able to get it out with the washing machine. Anxiously awaiting your response.
Also thank you for this video.
_--. He is teaching gold and you only care about a coffee stain? --_
Thankyou so much sir :)
Could you please upload a video on the application of bellman-ford i.e., linear programming problem by difference constraints
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
take edges in this order..... this prblm will be solved in on step
0 >1=4
0>2=5
1>2=-3
2>4=4
0>3=8
3>4=2
4>3=1
Thank you so much
Lectures explained well but sir,s pronouncation is distarcting
What if we take edges 0-2 and 0-1 before everyone else... you are bypassing the fact by considering those edges first whose both vertices are infinity. If 0-2 and 0-1 are taken first then in 1st iteration only other vertices are relaxed but it shouldn't be as shown in the textbook. Still confused how it's happening.
Thank you ❤️
so on average we are taking v-1 times for relaxing edges from source.So why can't i processes those edges from source itself.It will take |E| time complexity only??
This guy is fucking amazing
Heyyy, what if the graph contains a cycle of postive weights??
sir initial of the video u have 5 vertices and later 4 vertices
great!
hi tushar roy. i just want to know whats the difference between these three algorithms: Bellman-Ford, Dijkstra, and Floyd-Warshall algorithms. Which algorithm is more accurate to solve the shortest path?
thank you Tushar :). but do you think that its better to use the Floyd Warshall Algorithm? since it detects the shortest path from every other node??
aries cruz Bellman and Floyd use dynamic programming whereas Dijkstra uses greedy strategy. The Bellman-Ford and Dijkstra's algorithm output a shortest path from an input vertex r to all other vertices reachable from r, whereas Floyd's algorithm generate shortest path between all pairs of vertices of the digraph. Also, Dijkstra works with weighted digraph with non negative edges. Bellman Ford works with digraphs with no negative cycles. Next you can talk about their differences on the basis of difference in time complexities.
Why we need to do V-1 rounds: 13:05
please upload Single Source Longest Path Graph Algorithm......!
Can you upload same problem with the link failure?
How to find the longest path with the same algorithm ?
tussi gr8 ho :)
he is from nit allahabad and works at apple
I owe you my degree
how can a distance between 2 vertices be a negative number?
Weights are not always distances but are cost to reach that vertex which can we negative in some cases.
cost being negative, so this is better than free. i lack in understanding of real world application when this is the case.
wanna know why v-1 times? go to 12:59
it is weird how you pronounce V . Video= WE-deo. Vertices = WE-rtices xD
its not his mother tongue unlike yours :)
Tufayel Talha and two is thooo.. lol
V
he looks like sandeep maheshwari :|
Youre really rushing ahead with the concept without giving a clear explanation about the working of the algo .. same goes for your other videos
initialize with INT_MIN,INT_MIN,INT_MIN......
for each edge u,v,do:
if(dist[v]v)
dist[v]=dist[u]+weight(u->v).
In below commentof mine "vV1" is "V-1"
You have done a good video on this topic . but brother dont try to pretend as american . coz its sounding pretty bad ..
hello tushar , your word pronunciation is really bad , so can you please make your voice dry and use correct indian pronunciation
satsified with u anjoy
Slowly please Sir slowly..why so doing quickly !!
Hindi ma phara lai
I can't pay attention to the lecture because of that stain on your shirt.
oh good, you turned around.
Tushar, bro you aren't a teaching material ! Go find some other job ! Don't waste your time.