I think he's still working on it... Seriously going to a university for anything computer related is a joke. Most (not all) professors are stuck in the 80s/90s. For DB class I had to write a PHP app that talks to a DB. Ignoring the fact that I had to learn PHP, which is a travesty in its own right, The professor required us to print the code out and submit it. 100s of pages of code. I'm sure he didn't read it considering how fast he graded it and how many students he had. I would have learned so much and been better prepared for the workforce if he had us submit a GitHub repo. I graduated with a Masters in Software Engineering having never used Git, and every single job I've ever had uses Git. But I sure knew how to write a class in Java that handles fractions, having written that program for 3 different courses.
"[because of the complexity] i can't see anyone asking to do this by hand" you don't know the math teachers in France... thank you for this clear video!
You need to know the why behind the algorithm and not just the how. This video is great for a quick overview/review, but to really understand the algorithm you need to spend much more time understanding why the code does what it does.
@@lijieleow7158 Agree but not everyone needs someone else spending 30 min talking about it, for some it's enough with a quick explanation and then reading the code and thinking about it themselves for a couple of minutes about how it works.
Your video is absolutely amazing. I made a revision to my exam in one night with the help of the videos. I really appreciate the structure of the video with an example, pseudocode and time complexity. I can access the information I want in just 3 min! They are remarkable!
A perfectly clear explanation of the algorithm. Instead of live coding in Java or anything.. It did not even feel like you were rushing.. In under five minutes! - this is art.
I may be the wrong one here, but your explanation seems utterly insufficient (similar trend in your other videos), where you just show walkthrough of the algorithm with specific data, but do not really explain what different part means. For instance, here you did not explain what does that condition mean, why do we perform this test. All you needed to say at the beginning is that the algorithm is just repeatedly testing triangle inequality in conjunction with Bellman optimality principle (shortest paths are composed out of shortest paths).
It might not be a in-depth understanding but I still think this is the best explanation on youtube, it really allows you to get that first understanding on what is happening! Thanks!
@@malharjajoo7393 Because there is no need for it, it just shows you the most important parts in a few minutes. For some deep insights I would rather watch a lecture.
Your short videos literally help me a lot on learning those algorithms! Very concise and straightforward presentation of going through these processes! Thank you so much!!!
"No one can expect you to do this by hand"... *Looks at homework assignment for last week where I needed to do this*... *Looks at exam for today and how we need to know how to do it* But in all seriousness, Thank you for the help, and keep up the good work! These little short videos do much better at explaining than some long drawn out videos do : )
Thanks for this! I'm finding all of your videos helpful for my algorithms course. Do you think you could make one for Johnson's algorithm? It's the faster algorithm in O(V^2 log V + VE) time that computes all the shortest paths from all vertices (same problem that the Floyd-Warshall tries to solve).
I am a huge fan of how you explain these topics! Recommendation: I think a nice last shortest distance would be JOHNSON'S ALGORITHM to show how B.F. and Dijkstra can be utilized to find shortest path by re-weighting.
Well explained! Seems to be a small mistake 0:26 it's said negative cycles ain't allowed, but for Bellman-Ford algo negative cycles are allowed if I recall correctly from my lecture.
I think I get it! But it's just very confusing, it is called Bellman-Ford, ie, slide 14 courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf, runs on negative cycles (with detection), but can never output the shortest paths when there are negative cycles...
Correct me if i'm wrong, but you can detect infinite negative cycles in Bellman-Ford if you simply use the n'th iteration to see if anything has changed. Since it's supposed to run n-1 times, a change in the n'th iteration will indicate an infinite loop :)
I know it been 11 months, but if someone want that answered: Yes, you can do that. Other way of verifying the negative cycles is: After the algorithm of Bellman-Ford is called, you need to verify all the edges: uv = edge. u = origin v = destiny dist = distance from origin if (v.dist > uv.weight + u.dist) -> there is a negative cycle.
Thank you! Thank you very much! :-) I have just finally understood this (after half an hour of looking at my school notes)! Once more - thank you! :-) Greetings from Czech republic. :-)
no becouse dist 2 to 3 was faund that shortest path is via 1 where it produces 2 via 1 to 3 = 2 not 3 thats why its stored in the matrix not the graph if you revert back video this value was updated elier in video , this is why we looking total leess weight path , not less weight path via only one node
in short: if going from node A to node B is more expensive than going from node A to node C to node B, then thake that new path. A -> B > A -> C -> B. Thanks man!
What through me off for a bit is i, j, k starting at 1 is because the graph/vertices start at 1. if you're using indices or the lowest node is 0 or another number, then it needs to start at a different number.
If distance from (I to J through K) is shorter than the straight Distance from (I to J). Then Distance from (I to J) = Distance from (I to K) + Distance from(K to J).
You should probably mention how that three-loop formula is derived. And how this solution is actually a dynamic programming solution i.e. For each vertex k, we test whether it serves as a faster intermediary to two other nodes i and j. So dist[i][j] = min(dist[i][j], dist[i][k] +dist[k][j] ) or if k=1, i=2 and j=3, the formula asks, can we reach j from i faster using k as an intermediary.
This explanation would be so much better if you just included that "k is the node via which you try to find a shorter path", that made me realize what I was doing and sped up the time spent executing it by a lot
this is really the best explanation of most of the algorithms used in transport. Do you have any videos teaching maximum flow algorithms? (flow augmenting path and preflow push algorithm) or others like Dial's algorithm, minimun schedules and stuff like that? THX a lot !
You didn't explain the triple for loop, nor those variables (i,j,k) at all. Everything was clear up until that point where u just started simulating the code. Not ok, man
![NLE Choppa - Or What ft. 41 (Orchestra Mix) [Official Music Video]](http://i.ytimg.com/vi/biOFASEgSOM/mqdefault.jpg)
"I can't see anyone asking you to do it by hand" well i guess my professor didn't watch your video cause here i am doing an 8x8 matrix...
@@Daniel-eg1ov he might be done now
Are you still doing it?
did you die doing it :(
pls reply, we can help u :(
I think he's still working on it...
Seriously going to a university for anything computer related is a joke. Most (not all) professors are stuck in the 80s/90s. For DB class I had to write a PHP app that talks to a DB. Ignoring the fact that I had to learn PHP, which is a travesty in its own right, The professor required us to print the code out and submit it. 100s of pages of code. I'm sure he didn't read it considering how fast he graded it and how many students he had. I would have learned so much and been better prepared for the workforce if he had us submit a GitHub repo. I graduated with a Masters in Software Engineering having never used Git, and every single job I've ever had uses Git. But I sure knew how to write a class in Java that handles fractions, having written that program for 3 different courses.
"[because of the complexity] i can't see anyone asking to do this by hand"
you don't know the math teachers in France...
thank you for this clear video!
The best explanation! I'm tired of all other tedious 30min+ lectures, which made simple algorithms so complicated...
You need to know the why behind the algorithm and not just the how. This video is great for a quick overview/review, but to really understand the algorithm you need to spend much more time understanding why the code does what it does.
Hey
Cat-pics bros
@@lijieleow7158 Agree but not everyone needs someone else spending 30 min talking about it, for some it's enough with a quick explanation and then reading the code and thinking about it themselves for a couple of minutes about how it works.
Exactly!
Exactly!
Your video is absolutely amazing. I made a revision to my exam in one night with the help of the videos. I really appreciate the structure of the video with an example, pseudocode and time complexity. I can access the information I want in just 3 min! They are remarkable!
have exam in 5 hours and im binging these 4,5 minute algos, man god do exist in real life thank you micheal im eternally grateful
Currently resolving a 6 x 6 matrix wish me luck boys
Lucky you, i'm at an 8x8 one
are you finished yet ?
Matej Petras give him a bit more time
Maybe he is in last iteration will check back if it's finished or not.
Did u survive it ?
A perfectly clear explanation of the algorithm. Instead of live coding in Java or anything.. It did not even feel like you were rushing.. In under five minutes! - this is art.
my god this is the best explanation video for this algorithm. please make more
subscribed!
Really glad you enjoyed it. Thanks for watching!
I may be the wrong one here, but your explanation seems utterly insufficient (similar trend in your other videos), where you just show walkthrough of the algorithm with specific data, but do not really explain what different part means. For instance, here you did not explain what does that condition mean, why do we perform this test.
All you needed to say at the beginning is that the algorithm is just repeatedly testing triangle inequality in conjunction with Bellman optimality principle (shortest paths are composed out of shortest paths).
@@TheZubata225 Yes, Poor explanation. There is no insight into the ordering of the for loops. No mention of why this algorithm works.
It might not be a in-depth understanding but I still think this is the best explanation on youtube, it really allows you to get that first understanding on what is happening! Thanks!
@@malharjajoo7393 Because there is no need for it, it just shows you the most important parts in a few minutes. For some deep insights I would rather watch a lecture.
Dude, your under-x minute videos are insane. I understand the algorithms perfectly and am able to write good answers thanks to you!
Yo
I have an Algorithms final in a few hours and your videos are literally saving me.
Subscribed and please make more
Your short videos literally help me a lot on learning those algorithms! Very concise and straightforward presentation of going through these processes! Thank you so much!!!
Thank you a lot. It took me an hour reading the wiki page and I still did not get it until I see your video. Perfect explanation
Best Video 📹 on Floyd Warshell algo on RUclips that explains precisely in just 4 minutes. Great work sir.
final exam on algorithms in 6 hours, and your videos are saving my life, thank you
You explained this better in 4 minutes than my uni teacher did in 30 minutes of a 2 hours lecture, thanks man!
Impressive...Just 4 minutes and you made this algorithm crystal clear...
"No one can expect you to do this by hand"... *Looks at homework assignment for last week where I needed to do this*... *Looks at exam for today and how we need to know how to do it*
But in all seriousness, Thank you for the help, and keep up the good work! These little short videos do much better at explaining than some long drawn out videos do : )
Thanks a lot! This is, may be, the only one adequate step-by-step explanation of this algorithm. And definitely the best one that I have found.
Have never seen such a beautiful explanation under 5 min!!!!
Thank you!!
Truly the simplest and best explanation for this algorithm on the internet : )
loved it!
I can't express how much i appreciate these videos
Thank you, Vado!
1:18 oh boy idk if I'm ready for the meat of the algorithm
Love that you get straight to the point. Subbed.
Awesome videos!!!! Crisp, to-the-point explanation and covering all important aspects. Eagerly waiting for more videos
by far the best video i have seen , algo logic with code under 4 mins , amazing keep up the good work thanks
Better that an hour lecture from university. Thank you so much
💪🏼
I do not think I'll be doing as well in my algorithms class if not for your videos. Very clear and to the point.
Quality stuff right there!
I know I can believe the internet at teaching more that my professors.
this algorithm is actually so simple and intuitive. Thanks for explanation!
concise, visually easy to understand, masterfully done, thank you
"I can't see anyone asking you to do this by hand" *gasps*
Mi Maestra si lo pide carnal
Bro this is really the best explanation I’ve found on internet and it’s 4 minutes 🤣
Thanks for this! I'm finding all of your videos helpful for my algorithms course. Do you think you could make one for Johnson's algorithm? It's the faster algorithm in O(V^2 log V + VE) time that computes all the shortest paths from all vertices (same problem that the Floyd-Warshall tries to solve).
YES!! I havent found a good explanation for Johnson's yet!
Great video. Much easier explained than in our algorithm class.
Clear explanation with intuitive animation, great work.
Im going to pass my exam because of you thank you
I am a huge fan of how you explain these topics!
Recommendation:
I think a nice last shortest distance would be JOHNSON'S ALGORITHM to show how B.F. and Dijkstra can be utilized to find shortest path by re-weighting.
You taught me algorithms faster than any Indian guy on RUclips 😂. Even faster than my professor. Thanks.
oh my gosh that is a great explanation. It helps to figure out the code in 1 minute. Thanks alot
Straight to the point, short and very easily understandable 👍
Well explained! Seems to be a small mistake 0:26 it's said negative cycles ain't allowed, but for Bellman-Ford algo negative cycles are allowed if I recall correctly from my lecture.
Take a look at my Bellman-Ford videos: ruclips.net/video/9PHkk0UavIM/видео.html. If you had negative cycles, the algorithm would never end! ;)
I think I get it! But it's just very confusing, it is called Bellman-Ford, ie, slide 14 courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf, runs on negative cycles (with detection), but can never output the shortest paths when there are negative cycles...
Right! You can detect negative cycles, but a shortest path doesn't exist.
Correct me if i'm wrong, but you can detect infinite negative cycles in Bellman-Ford if you simply use the n'th iteration to see if anything has changed. Since it's supposed to run n-1 times, a change in the n'th iteration will indicate an infinite loop :)
I know it been 11 months, but if someone want that answered:
Yes, you can do that.
Other way of verifying the negative cycles is:
After the algorithm of Bellman-Ford is called, you need to verify all the edges:
uv = edge.
u = origin
v = destiny
dist = distance from origin
if (v.dist > uv.weight + u.dist) -> there is a negative cycle.
Thank you my friend for making your video available with subtitles in portuguese.
Thank you! Thank you very much! :-) I have just finally understood this (after half an hour of looking at my school notes)! Once more - thank you! :-)
Greetings from
Czech republic. :-)
Greatest 4 and a half minutes of my life..Great Video Man. Thanks
Hands down, best explanation out there.
I noticed a mistake in minute 3:10. dist[4][3] > dist [4][2] + dist [2][3] produces inf > 2
no becouse dist 2 to 3 was faund that shortest path is via 1 where it produces 2 via 1 to 3 = 2 not 3 thats why its stored in the matrix not the graph
if you revert back video this value was updated elier in video , this is why we looking total leess weight path , not less weight path via only one node
Oh boy you are wrong, our prof asked us to do that for 6x6 matrix.... so much fun.
Great video helped alot!
in short: if going from node A to node B is more expensive than going from node A to node C to node B, then thake that new path. A -> B > A -> C -> B.
Thanks man!
Are you a god or something?
You do this so effortlessly. Great work!
Thank you very much for your simple explanation
THIS IS JUST A GREAT VIDEO. Highly recommended!
Thanks for explanation
What through me off for a bit is i, j, k starting at 1 is because the graph/vertices start at 1.
if you're using indices or the lowest node is 0 or another number, then it needs to start at a different number.
Check out github.com/msambol/dsa/blob/master/shortest_path/floyd_warshall.py
your videos are awesome.. more than a 2 hour class!!
This video was very good! Thank you!
So to know the actual path, rather than just the cost, you would also need to store in each cell the next graph node to move to right?
Thanks for the video it really help me to undertand it :D
and my doubt was cleared in 4 minutes. thanks a lot
Best explanation yet, Thank you!!
Great video thanks for the effort and the upload!
Very Very Nice, hello from Brazil, thanks
Thanks, I finally understood what my professor wanted to teach us... :D
And, yeah, he expects us to do this by hand...
If distance from (I to J through K) is shorter than the straight Distance from (I to J).
Then Distance from (I to J) = Distance from (I to K) + Distance from(K to J).
Thanks a lot, it was very helpful. Very good explanation
Your video is pure gold.
Thanks! It was explained very well!
¡Thank you soo muuch!
Me ayudó bastante, saludos desde Bolivia!
Great and simple explanation, thanks!
This is amazing, just what I needed!!
Such an amazing explanation!!! OMG
You should probably mention how that three-loop formula is derived. And how this solution is actually a dynamic programming solution i.e. For each vertex k, we test whether it serves as a faster intermediary to two other nodes i and j. So dist[i][j] = min(dist[i][j], dist[i][k] +dist[k][j] ) or if k=1, i=2 and j=3, the formula asks, can we reach j from i faster using k as an intermediary.
This explanation would be so much better if you just included that "k is the node via which you try to find a shorter path", that made me realize what I was doing and sped up the time spent executing it by a lot
this was an amazing explanation, thank you so much!
thanks bro
you explained it better than my grandpa
Thank you so much. It really helped me understand easily.
Short and precise..well done
Crisp and Clear! Thanks a ton!!! More videos on advanced data structures would be helpful! :)
Best Explanation! Keep it Up Sir!
You explained in 4 minutes what my godawful professor couldn't explain in one and a half lectures.
Very clear and concise
Amazing Explanation!!!
Thank you very much Michael! Your explanation is very simple and understandable. You helped me a lot!
this is really the best explanation of most of the algorithms used in transport. Do you have any videos teaching maximum flow algorithms? (flow augmenting path and preflow push algorithm) or others like Dial's algorithm, minimun schedules and stuff like that? THX a lot !
Oh man that's awesome, too short, too precise.
I think negative weight cycles are allowed in Bellman-Ford, since it will just detect it.
Awesome, thank you very much!❤❤❤
Well explained in an Optimized way !
Thanks. That's very helpful.
So nicely explained
Can you also make videos about Edmonds-karp, Hopcroft-karp and Hungarian algorithms? Your videos are fantastic!
Fantastic explanation!
Amazing explanation! Thank you so much ! Just one quick question, when exaclty do you update the k ? once you reached the end of i row perhaps ?
awesome video,well explained !
Very well explained. Thanks.
Short and well explained
Thank you very much, it really helped. :)
You didn't explain the triple for loop, nor those variables (i,j,k) at all. Everything was clear up until that point where u just started simulating the code. Not ok, man
wow!! superbly explained.. what the erms in the formula describes!! any way nice video!
you are the best man...
Very helpful!