G-42. Floyd Warshall Algorithm

GfG-Problem Link: bit.ly/3JZlk4a
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79

[@namratam1522]

Thank you soooooo much!!! Understood!!!!!❤❤

[@sairam3351]

di[i][[j] = Min(d[i][k]+d[k][j]) right ?,u said d[j][k] dont know why

[@AJ-xc3ks]

@@sairam3351 min(d[i][k] + d[k][j]) is right..

[@shikharshiromani2728]

At 5:39, I think it should be min(d[i][k] + d[k][j])

[@takeUforward]

Yes, a small typo..

[@saranghae3720]

Hey, Striver, Pin this comment or write this in ur already pinned comment.

[@AbhrajyotiKundu00]

Yes, this is how addiction is built over Algorithms! Thank you Striver :)

[@anonymousanonymous7507]

Job lgi?

[@ITACHIUCHIHA-dr8sz]

@@anonymousanonymous7507 savage!!

[@mohanjha4397]

People say Graph is a difficult Topic, but after going through striver's i haven't faced any problem.so you are a genius.😊

[@saurabhsangam2737]

5:46 The equation should be minimum of (d [I] [k] + d [k] [j] ) for calculating for path I => k => j

[@andresfgalvis2010]

I can´t say enough, how much i love your videos

[@The_Shubham_Soni]

People say Graph is a difficult Topic, but after going through striver's series i haven't faced any problem. Moreover i find it Super Easy🤩

[@darshika8808]

understood! thanks Striver, the explanation is 🔥

[@lavanyam3224]

I feel like sitting in a maths class. Amazing explanation! You made a complex algorithm look very simple. Thanks a ton Striver!

[@mannumichel1925]

Understood and I too understood your effort which is incredible.

[@technologicalvivek7510]

Best graph playlist on youtube. You are the great sir.

[@shikharsrivastava8600]

Hey striver, the way you explained was quite commendable. Just at 26:58 , we should add extra if(matrix[i][k] != 1e9 && matrix[k][j] != 1e9) condition to make sure we don’t go via unreachable nodes.

[@user-kl3qv1sc8k]

No need for it since we are taking min of both so even if all of them are 1e9 the result will still be 1e9

[@ashurajput6916]

@@user-kl3qv1sc8k in case of negative edges followed by an 1e9 edge. this will pose problem. so i think if condition should be proposed

[@king-akash1479]

I really like the prompt that comes in which a message comes explaining what we should focus on. :)

[@priyanshkumar_iitd]

Yeah, very helpful

[@visase2036]

Amazing teaching as usual Striver. If you continue to teach this depth in Graph , you will soon device your own algorithm one day for sure.

[@PrabhatSingh-8533]

devise*

[@cinime]

Understood! Such a fantastic explanation as always, thank you very much!

[@MusaafirSonu]

After watching lots of video , I can only understand this video . Thank you Striver .❤

[@chidam333]

thank you so much ! i was panicking while revising as i couldn't get the intuition properly when revising!! Your 22:48 footnote was really helpful

[@Purvilicious]

Can't thank u enough! Striver 🔥

[@mayankkumar6997]

A small doubt at the last, if we apply dijkstra algorithm for finding all pair shortest path, then time complexity is = V E logV. But if it is complete graph then E approximate V^2. So final time complexity becomes V^3 logV, then how its better from floyd warshall algorithm!

[@takeUforward]

Usually you don't get complete graphs always..

[@srijankhatri4689]

I agree with mayank here. If you try to solve the ‘Find the city with smallest neighbours in a threshold’ leetcode problem using Dijkstra’s using set, the time taken is much higher than a simple Floyd warshal solution. Solving it through PQ gives a TLE.

[@user-jc5vo9sz3l]

A very fantastic explanation ❤

[@sukhpreetsingh5200]

understood just awesome explanation

[@stith_pragya]

Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@CodeMode9313]

Habibi katai bawaal macha rakhe ho ...1 number.chiz hai ye toh

[@arghyadeepchakraborty1977]

Great explanation!

[@user-yi4gx5zj9q]

Amazing explanation!

[@AYUSHKUMAR-xj4wc]

Awesome Explanation❤❤❤

[@IK-xk7ex]

Awesome. thank you for explanation

[@rohinianekar61]

understood, nice video, well explained

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@user-qz7tx5ce7e]

Hey Striver, i have an doubt the graph you use here,ends with infinity(in the final matrix) so does that mean there is no shortest path for such nodes???

[@herculean6748]

Thank you striver!

[@user-gc2fy1jb6p]

striver understood!!!! thankyou!!!👍

[@Chandraprakash-kx4ic]

love u striver...Thanku sooo much

[@preetkatiyar969]

THIS IS REAL THAT SOMETHING WE WANT AND I GURENTEED NO ONE CAN TEACH BETTER THAN THIS EVEN IN PAID COURSES OF LAKHS.

[@princepal8523]

amazing explanation *understood*

[@fatmayasser8188]

well explained thank you!

[@srinayan390]

u r the true gem🤩

[@TarunKumar-jg4jz]

Is it not possible to apply "bellman ford" for all the vertices and store in 2d array for result. ??

[@GyaanGrave]

The voice editing is OP💥

[@venkateshvenky2880]

Good explanation

[@vaibhavagarwal1479]

Hi! need help with the Space complexity Here striver mentioned that space complexity is n3(n*n*n) meaning we consider the space we use in solving the problem which here is the original matrix,lets take an example of bubble sort there also we use the same array to sort it, no other array is considered to solve but there the time complexity is not n but o(1) ? why is that am i missing onto something.. please reply if you have any clue.. Thankyou

[@jritzeku]

INTUITION(correct me if im wrong): We can think of 'via' as an intermediate node we must hop thru to get to destination( kind of like connecting flight(the second plane)). Therefore, after performing via 'nth' node, we have found shortest paths for node 'nth-1' as source where it touches nth node as intermediate node. Ex:After processing via node1, we were able to update shortest path from node0 to node2 because node1 as intermediate offered shorter path. See @17:10

[@UECAshutoshKumar]

Thank you sir 🙏

[@original_gangsta_]

Understood 🔥🔥

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@ShivamKendre-fc3su]

Thank you so much

[@ayushrai6699]

(V*E * logV) > (V^3)... right? As in worst case E is V*(V-1). So Floyd Warshall is better than Dijkstras for shortest path to all the nodes from multiple source in contrast to what striver said at 29:08

[@takeUforward]

E is V x V-1 is a very very very rare and dense graph..

[@ayushrai6699]

@@takeUforward Agreed but in interview we are supposed to give worst case time complexity... right? Or am I missing something?

[@ravisingh-el8np]

​@@ayushrai6699yes you're right don't worry

[@abhishek__anand__]

Great Video

[@AyushiPanday12]

Understood bhaiya!!

[@afredhussain7042]

understood 💯

[@Anurag_Badwahe]

I am thinking if i apply djikstra for all edges then the time complexity will be O(V.ElogV) . I am thinking it is better than O(V^³). Please correct me

[@p38_amankuldeep75]

understood🔥🔥

[@pavankaranam7469]

best.PERIOD.

[@DreamLife-05]

Understood 🙌💯

[@ankitmeena5637]

hats off to you bhaiya

[@siddharthkardam321]

striver my data is lost on your website after my mac has updated. I have made important notes on your website. What should I do now?

[@its_my_type]

Understood ❤❤

[@mdshohanurrahman4998]

understood💚

[@banothutharun2743]

understood brother

[@user-lw9dj8we7k]

Understood Sir

[@shreyashachoudhary480]

Amazing!

[@psionl0]

I know it is an old debate whether modifying the input counts as extra space but if you are instructed to do the solution IN-PLACE then I would argue that it shouldn't count as extra space. For example, Sorting is almost always done in-place and you never see the space complexity analysis include the size of the list that is being sorted.

[@aditya_raj7827]

understood sir ❤❤

[@anmolkaushik4576]

Understood!

[@garimakumari4346]

thanks man

[@user-tk2vg5jt3l]

Thank you bhaiya

[@sauravfarkade7032]

Understood!!

[@harshitsoni9103]

24:24 :that evil smile @takeUforward😁😂

[@destructaphoenix6679]

My favorite algo

[@-VLaharika]

Understood 👍

[@vardhamanbhandari5644]

understood!

[@harshdasila6680]

understooodddd

[@alokprasad6260]

Understood, any problem using this algorithm?

[@VishaliniT-f3g]

Understood 👍☺️

[@lonewolf-_-8634]

UNDERSTOOD

[@user-fs6qz7be2z]

Another point: Even if all the weights are positive, why Dijkstra might not be preferred over Floyd Warshall is because for Dijkstra, time complexity is V * E * log(V) For dense graphs, E ~ V^2 since E = V (V-1)/2 for a fully connected graph Making the time complexity V^3 * log(V) Tell me if I interpreted that correctly.

[@vibhorgupta641]

yes

[@pulkitgupta669]

Bro Djikstra time Complexity is O(V + E)Log V and if there is a dense graph then E = V^2 that makes it O(V^2 LogV) which is better than Floyd Warshall

[@CEBMANURBHAVARYA]

@@pulkitgupta669 bro, we are doing dijkstra for all the nodes so, time complexity will be V * whatever u calculated, which is at worst V^3 log(V), whereas floyd warshall has V^3

[@pulkitgupta669]

@@CEBMANURBHAVARYA Yeah sorry I miscalculated. Thank you for helping.

[@ACUCSPRADEEPB-up9ne]

Understood✌️

[@ROKADEADITYA]

Understanding

[@Ayeshasingh720]

understood😊😊

[@gautamsaxena4647]

understood bhaiya

[@manasranjanmahapatra3729]

Understood.

[@scaffgaming]

Why the code not giving integer overflow in the min function whenever adding with 1e9 plus something

[@heatedpants8437]

When two numbers that are close to INT_MAX are added, the result can exceed the maximum value that can be stored in an int, causing overflow. Overflow wraps around to negative values, which would then be incorrectly considered as a shorter path. Using 1e9 even if you add two paths with this maximum value, you get 2e9, which is still within the range of a 32-bit integer.

[@priyanshvatsal9791]

Understood 😇

[@advaithprasad2535]

Hi, can you please explain with an example why the "via" or the "k" loop must be outside, and won't work if it is inside? because i tried this code ''' for i in range(n): for j in range(n): for k in range(n): d[i][j] = min(d[i][j], d[i][k]+d[k][j]) ''' and it gives wrong answer but ''' for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j], d[i][k]+d[k][j]) ''' gives correct answer I am very confused. Please help! Thanks in advance :)

[@harshith4549]

you didn't watched the lecture right!! you would have understood it right away if yes. So hear me out, the d[i][j] = min(d[i][j], d[i][k]+d[k][j]) formula you are calculating is done for the node i to node j via k. In the the first algo you are changing the k(the node you are passing through to reach j) which will use shorter distances that are not calculated yet. If you do a dry run on second algo, you will understand that d[i][k] and d[k][j] values are constant for that iteration of k which is not the case in the first algo. Not understanding!! Just take a pen and paper and do a dry run.

[@harshitjaiswal9439]

understood.

[@sanamdeepsingh7914]

Understood

[@vanshikakumari5744]

understood

[@AmanGupta-ib5ss]

understood :)

[@vishalbairagi7238]

my code is not working when i use INT_MAX when node is unreachable, but same code is working when i use 1e9 in gfg.

[@ajaybabupatel1665]

understood ++, Addicted bruhh with graph playlist, Thanks a lot @raj

[@KunalSingh-kn2ij]

why the code is giving wrong output if we are using INT_MAX instead of 1e9?

[@shivasai7707]

Out of bounds

[@googlepay4295]

even if you add +1 to int max it goes out of bounds and produces error . hence always use 1e9 or 1e8 for graph algos

[@kashviagrawal4553]

understood😃😃

[@pratyushpandey6139]

why if == -1 ? condition not get it

[@rohitkumar-dc3xb]

One thing i don't get it u say even if we use same matrix still we are using O(n*n) time complexity, but in array problems if we try to find the answer using same array without using any extra space we say TC is O(1). Isn't it contracdicting ? Btw nice explaination.....

[@gouthamikarshikalam4037]

why am i getting wrong output if iam using INT_MAX instead of 1e9??

[@takeUforward]

Because INT_MAX. + a valuue > INT_MAX and cannot be stored in int

[@namamiNarayana]

Understood Sir! :) Thank you! _/\_ ^^

[@manishpandey2725]

understod

[@dishant930]

Love your content striver just want to tell you forgot to write the if statement -: if(matrix[i][k] != 1e9 && matrix[k][j]!=1e9) before matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]); If we dono't add this condition then if fail for below test case For Input: 3 0 -1 -1 -1 0 -2 -1 -1 0 Your Output: 0 -1 999999998 999999998 0 -2 -1 -1 0 Expected Output: 0 -1 -1 -1 0 -2 -1 -1 0

[@gaganagarwal7218]

void shortest_distance(vector&mat){ int n = mat.size(); for(int via=0; via

[@KratosProton]

great

[@aniruddhapaul6728]

where is the mathematical proof, that the approach gives the correct ans?