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 :-)
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!!!
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
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??
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! :)
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
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??
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.
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.
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.
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....
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??
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!
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.
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.
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.
Really love your videos!Your enthusiasm and will to teach is pretty much evident through your videos.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 :-)
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.
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
Been looking around for exactly this kinda video for so long. Everything at one place, thanks mate!
Have my daa exam day after tomorrow. This video helped me complete an imp topic in a span of 20 mins. 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??
excellent...ur approach of teaching is excellent. directly gets corelated to code implementation ( maps, parents etc.) thanks..
Thanks a lot. The most comprehensive lecture on belman ford :)
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! :)
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
I really like your simple teaching
Very helpful even after 7 years
thanks for explaining cleary this algorithm. I had confusion regarding v-1 iterations thanks for clearing it.👍
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 !
Every video is a gem sir.
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.
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.
love you man, really like your teaching, thanks a lot, cheers
Best vedio for Bellmenford.....Thankuuu
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.
U r great man...........Thanks a lot...Wish i could withdraw my college fees Give it to you...
You should use vertices name as a, b, c, etc and weights as 1, 2, 3 etc, using both numeric can confuse many people!
Space complexity should be O(E), not O(V). E>V. We need to store every edge to iterate through them.
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
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....
thnks sir... excellent explanation.. keep it up
@Tushar Can you please explain why Dijkstra's algorithm does not work if there are negative weight edges?
very well explained. Thank you :)
nice vedio .worth watching.👍
Good explanation. It was a little disorienting when you flipped the formula in iteration 2.
great explained......!!!!
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??
Excellent work Sir :)
Awesome !! can you please post Floyd Warshall too... Thanks in advance
+Tushar Roy Thank you so much :)
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.
Very nice explanation! :) little suggestion, just improve video quality.
Thank u sir........🙏🙏
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
u r correct, u can store changed vertices in a queue..
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!
Can you upload same problem with the link failure?
Heyyy, what if the graph contains a cycle of postive weights??
it was confusing at the beginning but I got it.
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. it was awesome :)
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??
How u have time to make these nice videos?..... @Apple developer :) Hats Off to ur Work...
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.
sir initial of the video u have 5 vertices and later 4 vertices
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??
Why we need to do V-1 rounds: 13:05
very helpful, thank you
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? --_
How to find the longest path with the same algorithm ?
Thank you
please upload Single Source Longest Path Graph Algorithm......!
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.
Thank you ❤️
Thank you so much
wanna know why v-1 times? go to 12:59
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
This guy is fucking amazing
great!
Lectures explained well but sir,s pronouncation is distarcting
tussi gr8 ho :)
he is from nit allahabad and works at apple
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
I owe you my degree
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).
V
he looks like sandeep maheshwari :|
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 !!
I can't pay attention to the lecture because of that stain on your shirt.
oh good, you turned around.
Hindi ma phara lai
Tushar, bro you aren't a teaching material ! Go find some other job ! Don't waste your time.