Floyd-Warshall algorithm in 4 minutes

[@Amanda-sg2pu]

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

[@andrea1955]

@@Daniel-eg1ov he might be done now

[@MewPurPur]

Are you still doing it?

[@markuslinke9206]

did you die doing it :(

[@El-ni8ph]

pls reply, we can help u :(

[@gogokowai]

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.

[@shyndard]

"[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!

[@qingouyang7913]

The best explanation! I'm tired of all other tedious 30min+ lectures, which made simple algorithms so complicated...

[@lijieleow7158]

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.

[@dane-se7609]

Hey Cat-pics bros

[@johndoesson]

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

[@maitreyo137]

Exactly! Exactly!

[@zihanzhong921]

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!

[@sinefinehabitarevolo]

my god this is the best explanation video for this algorithm. please make more subscribed!

[@MichaelSambol]

Really glad you enjoyed it. Thanks for watching!

[@TheZubata225]

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

[@malharjajoo7393]

@@TheZubata225 Yes, Poor explanation. There is no insight into the ordering of the for loops. No mention of why this algorithm works.

[@alanwang4178]

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!

[@Pieczorka]

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

[@nolanrudolph5463]

Currently resolving a 6 x 6 matrix wish me luck boys

[@virtuosek4763]

Lucky you, i'm at an 8x8 one

[@catlord69]

are you finished yet ?

[@yazdaspaz6240]

Matej Petras give him a bit more time

[@shubhambhardwaj2853]

Maybe he is in last iteration will check back if it's finished or not.

[@IStMl]

Did u survive it ?

[@yingdawang7327]

Impressive...Just 4 minutes and you made this algorithm crystal clear...

[@plasticgodzilla1]

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.

[@techvishnuyt]

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

[@hamzadar2029]

I have an Algorithms final in a few hours and your videos are literally saving me. Subscribed and please make more

[@urmilshroff]

Dude, your under-x minute videos are insane. I understand the algorithms perfectly and am able to write good answers thanks to you!

[@lucutes2936]

Yo

[@gabrielstancu4986]

You explained this better in 4 minutes than my uni teacher did in 30 minutes of a 2 hours lecture, thanks man!

[@diya9707]

"I can't see anyone asking you to do this by hand" *gasps*

[@herrjorgedark]

Mi Maestra si lo pide carnal

[@Jkaramcs]

final exam on algorithms in 6 hours, and your videos are saving my life, thank you

[@helenh2442]

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!!!

[@CrystalENVT]

"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 : )

[@soumyadeep_bi]

Truly the simplest and best explanation for this algorithm on the internet : ) loved it!

[@soojimoo]

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

[@nishantgurrapadi]

YES!! I havent found a good explanation for Johnson's yet!

[@CallmeKaram]

Best Video 📹 on Floyd Warshell algo on KZbin that explains precisely in just 4 minutes. Great work sir.

[@mattsupertramp6506]

1:18 oh boy idk if I'm ready for the meat of the algorithm

[@BayCon632]

Love that you get straight to the point. Subbed.

[@TriNguyen-xi8ji]

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

[@Virus-ke8xj]

Have never seen such a beautiful explanation under 5 min!!!! Thank you!!

[@BB_Harunya]

concise, visually easy to understand, masterfully done, thank you

[@ffatheranderson]

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.

[@vado4003]

I can't express how much i appreciate these videos

[@MichaelSambol]

Thank you, Vado!

[@ginnyli2913]

this algorithm is actually so simple and intuitive. Thanks for explanation!

[@nicoleblandin3289]

Im going to pass my exam because of you thank you

[@jayeshborgaonkar9166]

by far the best video i have seen , algo logic with code under 4 mins , amazing keep up the good work thanks

[@imRJD14]

Bro this is really the best explanation I’ve found on internet and it’s 4 minutes 🤣

[@bibomisa6999]

Quality stuff right there! I know I can believe the internet at teaching more that my professors.

[@toby0622]

Clear explanation with intuitive animation, great work.

[@Daniel-iy1ed]

Better that an hour lecture from university. Thank you so much

[@MichaelSambol]

💪🏼

[@Redart15]

Oh boy you are wrong, our prof asked us to do that for 6x6 matrix.... so much fun. Great video helped alot!

[@BrainDeadZombies]

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.

[@summussaer501]

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

[@iforce2d]

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?

[@harshavardhankk18]

You taught me algorithms faster than any Indian guy on KZbin 😂. Even faster than my professor. Thanks.

[@aanshuk]

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.

[@MichaelSambol]

Check out github.com/msambol/dsa/blob/master/shortest_path/floyd_warshall.py

[@elbonkadillo]

Great video. Much easier explained than in our algorithm class.

[@storiesbeneaththesurface1942]

thanks bro you explained it better than my grandpa

[@Jekica9977]

Straight to the point, short and very easily understandable 👍

[@joelarsen806]

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.

[@ashjosh3963]

Awesome videos!!!! Crisp, to-the-point explanation and covering all important aspects. Eagerly waiting for more videos

[@_equal9817]

Thanks for explanation

[@livb4139]

Love the graphical representation

[@ritikchail7330]

Short and well explained

[@TopAAA]

I think negative weight cycles are allowed in Bellman-Ford, since it will just detect it.

[@Maen963]

Very clear and concise

[@alwaysisnever5896]

oh my gosh that is a great explanation. It helps to figure out the code in 1 minute. Thanks alot

[@thetedmang]

Hands down, best explanation out there.

[@glaucoa.9214]

Thank you my friend for making your video available with subtitles in portuguese.

[@youssef.elmoumen]

Thank you very much for your simple explanation

[@hetias]

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!

[@SahilKumar-pt3np]

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

[@gabrielchu5798]

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.

[@MichaelSambol]

Take a look at my Bellman-Ford videos: kzbin.info/www/bejne/b4GrnJ5misapf68. If you had negative cycles, the algorithm would never end! ;)

[@gabrielchu5798]

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

[@MichaelSambol]

Right! You can detect negative cycles, but a shortest path doesn't exist.

[@laurenbouhnik]

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 :)

[@DarkFalconDF]

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.

[@jirifrantal2236]

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. :-)

[@AdminDarkraiRSK]

thankyou for saving 20+ mins

[@EddyFisico]

This video was very good! Thank you!

[@cesaraumejia]

THIS IS JUST A GREAT VIDEO. Highly recommended!

[@pythonita8893]

I noticed a mistake in minute 3:10. dist[4][3] > dist [4][2] + dist [2][3] produces inf > 2

[@lunai3225]

still saving students lives over here :))

[@IFennecYouCODM]

and my doubt was cleared in 4 minutes. thanks a lot

[@hrishabhchoudhary2700]

Aren't negative edges allowed in Dijkstra's? All 3 algos can work fine with negative edges. What is not allowed are negative cycles. Dijkstra's would continue forever in case of negative cycles' presence and Bellman-Ford can detect it's presence.

[@maneesh1558]

Amazing Explanation!!!

[@carlosdanielpohlod4388]

Very Very Nice, hello from Brazil, thanks

[@smnadim21]

your videos are awesome.. more than a 2 hour class!!

[@vinhnguyen3095]

Nice but I wonder why it could work perfectly like that. The previous steps can support the next step even though they are not the final result. Why?

[@niiquartey4500]

Are you a god or something? You do this so effortlessly. Great work!

[@shaileshnavale1819]

Short and precise..well done

[@kautukraj]

Very helpful!

[@abolfazljahangir1651]

Awesome, thank you very much!❤❤❤

[@trestenpool9045]

Best explanation yet, Thank you!!

[@UhelUhel]

Warshall, here I come. Thanks Micheal.

[@Medvednic]

Great and simple explanation, thanks!

[@sarthaksharma9322]

Greatest 4 and a half minutes of my life..Great Video Man. Thanks

[@miguelhuayllas1484]

Thanks for the video it really help me to undertand it :D

[@XenoAlbedo]

You explained in 4 minutes what my godawful professor couldn't explain in one and a half lectures.

[@stephydanglades9893]

i don't understand why for k = 4 we have dist [1][2] because 1 is not a predecessor of 4

[@MyNameIsNotNick]

thanks for the simplicity

[@foalborn]

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 !

[@sevilakts]

Thanks. That's very helpful.

[@zach990il4]

ok you can find the shortest path weight but how you can find the actual path from this number ?

[@jaimesedore643]

this was an amazing explanation, thank you so much!

[@samridhamanshrestha3243]

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.

[@asd33033]

Thanks, I finally understood what my professor wanted to teach us... :D And, yeah, he expects us to do this by hand...

[@roshanpawar8704]

Thank you so much. It really helped me understand easily.

[@ProfessionalTycoons]

Your video is pure gold.

[@junhuixu1641]

Can you also make videos about Edmonds-karp, Hopcroft-karp and Hungarian algorithms? Your videos are fantastic!

[@parthgadoya5690]

Well explained in an Optimized way !

[@jardelnunes6363]

Such an amazing explanation!!! OMG

[@Paul-qn7qv]

3:10 Shouldn't there be "-1 + 3"?

[@sidharthdash841]

So nicely explained

[@paritoshpandey5103]

Oh man that's awesome, too short, too precise.

[@danielamontecinos9558]

¡Thank you soo muuch! Me ayudó bastante, saludos desde Bolivia!

[@assemalbitar8069]

you are the best man...

[@michaelscott8572]

How do I know what the shortest path is? Because thatsÄ just the shortest connection between two vertices?

[@rothenbergt]

Great video thanks for the effort and the upload!

[@FutureWiredTec]

Thanks! It was explained very well!

[@mignonhagemeijer3726]

does anyone know how to reverse this? I need to be able to compute back to the original matrix