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!

[@De1n1ol]

math teachers? You study graphs in math?😶‍🌫 What kind of math class is that?

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

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

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

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

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

[@yingdawang7327]

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

[@Jkaramcs]

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

[@vado4003]

I can't express how much i appreciate these videos

[@MichaelSambol]

Thank you, Vado!

[@hamzadar2029]

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

[@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 ?

[@Virus-ke8xj]

Have never seen such a beautiful explanation under 5 min!!!! 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!!!

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

[@mattsupertramp6506]

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

[@CallmeKaram]

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

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

[@pythonita8893]

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

[@tomaszszczepaniak2101]

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

[@BayCon632]

Love that you get straight to the point. Subbed.

[@soumyadeep_bi]

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

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

[@toby0622]

Clear explanation with intuitive animation, great work.

[@kisaflwr]

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

[@herrjorgedark]

Mi Maestra si lo pide carnal

[@jayeshborgaonkar9166]

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

[@Daniel-iy1ed]

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

[@MichaelSambol]

💪🏼

[@ginnyli2913]

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

[@bibomisa6999]

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

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

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

[@thetedmang]

Hands down, best explanation out there.

[@elbonkadillo]

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

[@ashjosh3963]

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

[@Jekica9977]

Straight to the point, short and very easily understandable 👍

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

[@imRJD14]

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

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

[@alwaysisnever5896]

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

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

[@sarthaksharma9322]

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

[@trestenpool9045]

Best explanation yet, Thank you!!

[@MuhammadQasim-ej6hc]

one issue i noticed, the weight going from 4-3 is 2, thanks so much for the video

[@cesaraumejia]

THIS IS JUST A GREAT VIDEO. Highly recommended!

[@nicoleblandin3289]

Im going to pass my exam because of you thank you

[@EddyFisico]

This video was very good! Thank you!

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

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

[@IFennecYouCODM]

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

[@_equal9817]

Thanks for explanation

[@rothenbergt]

Great video thanks for the effort and the upload!

[@Redart15]

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

[@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?

[@niiquartey4500]

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

[@smnadim21]

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

[@quirkygears]

This is amazing, just what I needed!!

[@Medvednic]

Great and simple explanation, thanks!

[@jardelnunes6363]

Such an amazing explanation!!! OMG

[@miguelhuayllas1484]

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

[@UhelUhel]

Warshall, here I come. Thanks Micheal.

[@shaileshnavale1819]

Short and precise..well done

[@junhuixu1641]

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

[@FutureWiredTec]

Thanks! It was explained very well!

[@TopAAA]

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

[@carlosdanielpohlod4388]

Very Very Nice, hello from Brazil, thanks

[@livb4139]

Love the graphical representation

[@jaimesedore643]

this was an amazing explanation, thank you so much!

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

[@summerlee6416]

this is quite clear but could you please add some graphics that illustrate step by step?

[@abolfazljahangir1651]

Awesome, thank you very much!❤❤❤

[@harshavardhankk]

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

[@matanavnon]

Thank you very much Michael! Your explanation is very simple and understandable. You helped me a lot!

[@goyalvipra786]

Best Explanation! Keep it Up Sir!

[@ProfessionalTycoons]

Your video is pure gold.

[@roshanpawar8704]

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

[@danielamontecinos9558]

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

[@XenoAlbedo]

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

[@paritoshpandey5103]

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

[@fcmello1]

Thanks a lot, it was very helpful. Very good explanation

[@storiesbeneaththesurface1942]

thanks bro you explained it better than my grandpa

[@arielhy111]

thank you for this video! can you make a seidel algorithm too?

[@girojudo]

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 ?

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

[@parthgadoya5690]

Well explained in an Optimized way !

[@nowanknows8979]

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

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

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

[@asd33033]

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

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

[@Maen963]

Very clear and concise

[@MilanNedic94]

From 2 to 4 going over 3 (k = 3, i = 2, j = 4, @3:26), path is 3 + 2, not 2 + 2, so the matrix location [2][4] should be 5?

[@belhsankhaoula8913]

yes it would be 5 but we're looking for the shortest path possible

[@TheFitFiddler]

Crisp and Clear! Thanks a ton!!! More videos on advanced data structures would be helpful! :)

[@sevilakts]

Thanks. That's very helpful.

[@ritikchail7330]

Short and well explained

[@lunai3225]

still saving students lives over here :))

[@egzonademi5681]

Very well explained. Thanks.

[@kimnguyen1227]

I like the tracing of the algorithm and really grateful for your videos,. What I find lacking in a lot of dp tutorials is how the building blocks were built. For example, dist4][1] is looking at the path from v 4--> 2 and 2 --> 1. Still, how do you compose a dp problem knowing this?