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?

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

[@king-akash1479]

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

[@priyanshkumariitd]

Yeah, very helpful

[@lavanyam3224]

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

[@darshika8808]

understood! thanks Striver, the explanation is 🔥

[@andresfgalvis2010]

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

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

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

[@cinime]

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

[@mannumichel1925]

Understood and I too understood your effort which is incredible.

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

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

[@saurabhsangam2737]

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

[@CodeMode9313]

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

[@user-jc5vo9sz3l]

A very fantastic explanation ❤

[@stith_pragya]

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

[@sukhpreetsingh5200]

understood just awesome explanation

[@AYUSHKUMAR-xj4wc]

Awesome Explanation❤❤❤

[@user-yi4gx5zj9q]

Amazing explanation!

[@arghyadeepchakraborty1977]

Great explanation!

[@herculean6748]

Thank you striver!

[@IK-xk7ex]

Awesome. thank you for explanation

[@preetkatiyar969]

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

[@rohinianekar61]

understood, nice video, well explained

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@Chandraprakash-kx4ic]

love u striver...Thanku sooo much

[@user-gc2fy1jb6p]

striver understood!!!! thankyou!!!👍

[@GyaanGrave]

The voice editing is OP💥

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

[@srinayan390]

u r the true gem🤩

[@princepal8523]

amazing explanation *understood*

[@venkateshvenky2880]

Good explanation

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@AyushiPanday12]

Understood bhaiya!!

[@original_gangsta_]

Understood 🔥🔥

[@TarunKumar-jg4jz]

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

[@UECAshutoshKumar]

Thank you sir 🙏

[@ShivamKendre-fc3su]

Thank you so much

[@abhishek__anand__]

Great Video

[@harshitsoni9103]

24:24 :that evil smile @takeUforward😁😂

[@afredhussain7042]

understood 💯

[@p38_amankuldeep75]

understood🔥🔥

[@DreamLife-05]

Understood 🙌💯

[@pavankaranam7469]

best.PERIOD.

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

[@its_my_type]

Understood ❤❤

[@ankitmeena5637]

hats off to you bhaiya

[@destructaphoenix6679]

My favorite algo

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

[@mdshohanurrahman4998]

understood💚

[@user-lw9dj8we7k]

Understood Sir

[@shreyashachoudhary480]

Amazing!

[@user-tk2vg5jt3l]

Thank you bhaiya

[@garimakumari4346]

thanks man

[@sauravfarkade7032]

Understood!!

[@aditya_raj7827]

understood sir ❤❤

[@lonewolf-_-8634]

UNDERSTOOD

[@anmolkaushik4576]

Understood!

[@harshdasila6680]

understooodddd

[@-VLaharika]

Understood 👍

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

[@gautamsaxena4647]

understood bhaiya

[@ankitpathak1604]

understood!

[@ACUCSPRADEEPB-up9ne]

Understood✌️

[@alokprasad6260]

Understood, any problem using this algorithm?

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

[@namamiNarayana]

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

[@ROKADEADITYA]

Understanding

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

[@manasranjanmahapatra3729]

Understood.

[@venutalla5932]

Understood

[@sumitchakrabortystudy651]

understood

[@vaibhavverma6120]

why we are using (via) loop first i.e for every i,j check for via k first ...... why cant we check for a particular i,j with all the vias first and then move to next i,j(means we take k loop as the third loop instead of first loop)?

[@priyanshvatsal9791]

Understood 😇

[@abdullah2509]

understood.

[@AmanGupta-ib5ss]

understood :)

[@kashviagrawal4553]

understood😃😃

[@ajaybabupatel1665]

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

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

[@pratyushpandey6139]

why if == -1 ? condition not get it

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

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

[@vaalarivan_p]

1:10 - 16:00 23:00 - 24:35

[@snehamaurya3659]

what about the conditions where infinity is added to infinity and gives negative result ?

[@lakshmanchandukondreddy1720]

To avoid that we have to if condition like this if(matrix[i][k]!=1e9 and matrix[k][j]!=1e9)

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

[@durgeshjadhav01]

nice

[@manishpandey2725]

understod

[@KratosProton]

great

[@bbcs6392]

Can I implement floyad warshall using adjacency list.If yes tell me how with proper explanation

[@saitejadamaraju5408]

convert it into adjacency matrix

[@shubhampitale1067]

So what I basically did was to apply dijkstra algorithm to find the shortest path for a source. We take all the vertices as source one by one and apply dijkstra algorithm for it. Here is code for your reference. int n=matrix.size(); vectoradj[n]; for(int i=0;i

[@soumm0]

understand

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

[@akashsahu2571]

yes

[@manoranjankumarjha3776]

🔥🔥

[@muskangupta7522]

Hi , what if i make my loop like this , For ( i loop ) For ( j loop ) For ( intermediate loop) ..i am getting wrong ans if i make loop like this , can you tell why intermediate loop should be on first , acc to me it can be at last also.

[@piyushrajput0_]

I also have same doubt if you know its answer then please reply

[@hemendrasrivastava4634]

If you think about it, you are actually changing the algorithm by doing this. In the original algorithm you are updating the matrix for each intermediate vertex one by one. In your case you are going to update each node for each via at one go which is actually a different algorithm. Think of it like bellman ford, the changes take n steps to propogate to all nodes. You are updating each node at one go without the changes propogating

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

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