G-42. Floyd Warshall Algorithm

Подписаться 622 тыс.

Просмотров 184 тыс.

50% 1

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

Опубликовано:

9 окт 2022

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 243

@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 8 месяцев назад

@@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 7 месяцев назад

Job lgi?

@ITACHIUCHIHA-dr8sz 2 дня назад

@@anonymousanonymous7507 savage!!

@mohanjha4397 4 месяца назад

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

@andresfgalvis2010 Год назад

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

@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 11 месяцев назад

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

@priyanshkumariitd Месяц назад

Yeah, very helpful

@darshika8808 Год назад

understood! thanks Striver, the explanation is 🔥

@lavanyam3224 4 месяца назад

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

@The_Shubham_Soni 10 месяцев назад

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 8 месяцев назад

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 11 дней назад

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

@saurabhsangam2737 11 месяцев назад

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

@chidam333 3 месяца назад

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

@MusaafirSonu 3 месяца назад

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

@Purvilicious 10 месяцев назад

Can't thank u enough! Striver 🔥

@sukhpreetsingh5200 Год назад

understood just awesome explanation

@user-jc5vo9sz3l Год назад

A very fantastic 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.

@CodeMode9313 11 месяцев назад

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

@stith_pragya 7 месяцев назад

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

@user-yi4gx5zj9q 10 месяцев назад

Amazing explanation!

@AYUSHKUMAR-xj4wc Год назад

Awesome Explanation❤❤❤

@arghyadeepchakraborty1977 Год назад

Great explanation!

@rohinianekar61 Год назад

understood, nice video, well explained

@IK-xk7ex 11 месяцев назад

Awesome. thank you for explanation

@vakhariyajay2224 Год назад

Thank you very much. You are a genius.

@herculean6748 Год назад

Thank you striver!

@Chandraprakash-kx4ic Год назад

love u striver...Thanku sooo much

@GyaanGrave Год назад

The voice editing is OP💥

@user-gc2fy1jb6p Год назад

striver understood!!!! thankyou!!!👍

@princepal8523 Год назад

amazing explanation *understood*

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

@venkateshvenky2880 Год назад

Good explanation

@srinayan390 Год назад

u r the true gem🤩

@fatmayasser8188 День назад

well explained thank you!

@jritzeku 4 месяца назад

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

@udaytewary3809 Год назад

Understood bhaiya 🙏❤️

@UECAshutoshKumar 7 месяцев назад

Thank you sir 🙏

@AyushiPanday12 Год назад

Understood bhaiya!!

@original_gangsta_ Год назад

Understood 🔥🔥

@ShivamKendre-fc3su 6 месяцев назад

Thank you so much

@harshitsoni9103 Год назад

24:24 :that evil smile @takeUforward😁😂

@abhishek__anand__ Год назад

Great Video

@afredhussain7042 5 месяцев назад

understood 💯

@ankitmeena5637 Год назад

hats off to you bhaiya

@psionl0 2 дня назад

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.

@p38_amankuldeep75 Год назад

understood🔥🔥

@user-qz7tx5ce7e 8 месяцев назад

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

@DreamLife-05 Год назад

Understood 🙌💯

@shreyashachoudhary480 Год назад

Amazing!

@TarunKumar-jg4jz Год назад

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

@destructaphoenix6679 Год назад

My favorite algo

@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 10 месяцев назад

@@ayushrai6699yes you're right don't worry

@pavankaranam7469 Год назад

best.PERIOD.

@mdshohanurrahman4998 Год назад

understood💚

@aditya_raj7827 4 месяца назад

understood sir ❤❤

@user-lw9dj8we7k 8 месяцев назад

Understood Sir

@its_my_type Месяц назад

Understood ❤❤

@garimakumari4346 Год назад

thanks man

@darish155 Год назад

Understood!

@user-tk2vg5jt3l 2 месяца назад

Thank you bhaiya

@harshdasila6680 Год назад

understooodddd

@-VLaharika Год назад

Understood 👍

@vardhamanbhandari5644 Год назад

understood!

@lonewolf-_-8634 Год назад

UNDERSTOOD

@mriduljain6809 Год назад

Understood!!

@ACUCSPRADEEPB-up9ne Год назад

Understood✌️

@ROKADEADITYA Год назад

Understanding

@ajaybabupatel1665 Год назад

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

@gautamsaxena4647 2 месяца назад

understood bhaiya

@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 11 месяцев назад

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 11 месяцев назад

@@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 11 месяцев назад

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

@namamiNarayana Год назад

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

@manasranjanmahapatra3729 Год назад

Understood.

@vaalarivan_p Год назад

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

@Ayeshasingh720 2 дня назад

understood😊😊

@vaibhavagarwal1479 6 месяцев назад

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

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

@AmanGupta-ib5ss Год назад

understood :)

@priyanshvatsal9791 Год назад

Understood 😇

@abdullah2509 Год назад

understood.

@sanamdeepsingh7914 Год назад

Understood

@TonyStark-ct8xd Год назад

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

@alokprasad6260 Год назад

Understood, any problem using this algorithm?

@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

@rohitkumar-dc3xb 29 дней назад

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

@kashviagrawal4553 3 месяца назад

understood😃😃

@KratosProton Год назад

great

@aniruddhapaul6728 8 месяцев назад

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

@ajoydev8876 6 месяцев назад

5.39, a small correction, dis[i][j] = min(dis[i] [k] + dis[k] [j]);

@manishpandey2725 Год назад

understod

@manoranjankumarjha3776 Год назад

🔥🔥

@ankitshaw_3060 Год назад

For someone thinking whether can we detetct negative cycle similarly as we detected here by checking the distance[source]

@akashsahu2571 Год назад

yes

@soumm0 Год назад

understand

@scaffgaming 28 дней назад

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

@heatedpants8437 16 дней назад

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.