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
@@anonymousanonymous7507 he's pursuing MTech in CSE from IIT Guwahati. Har jagah cool nahi banna hota, strangers ke saamne cool banne ki naakam koshish karne se achha hai khudpe mehnat karo aur aage badho life me
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.
Floyd Warshal Algorithm: 1) Initialise dp(N x N) with Infinity. 2) Update dp[i][i] = 0; 3) Update given edge's weight in dp. 4) We need to find the minDistance from i to j via each node. 5) dp[i][j] = dp[i][via] + dp[via][j]; 6) As a result, dp will have the min distance from any-to-any nodes of graph.
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
23:14 at this graph at nth itteration [0][0] via 2 is [0][2] + [2][0] is equal to -5 +2 = -3 which is smaller than zero hence It confirms negative cycle because [I][I] should be zero
(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
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!
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.
@mayankkumar6997: The ELogV for Djikstra's algorithm is Worst Case complexity. It's actual Elog(V^2 ) because in the worst case, the min heap will have V*(V-1) entries in the heap, which approximated to V^2. And that is O(2ElogV), which is O(ElogV). If you repeat that for V vertices, then time complexity is V*O(ElogV) . That outside V cannot be multipled with E. Another thing to note is that FloydWarshal is always O(V^3)
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.
@@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
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.
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???
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
I have a small doubt here, while computing the shortest path by considering node 1 as the intermediary, why are we computing values from that matrix where 0th node is considered as intermediary and not the original matrix? Can anyone help me out with this? Thanks
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.....
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.
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
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
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)?
why are you saying...when undirected graph will be given change it to directed by making two edges...it's not already understood because of the adjacency matrix( which already has edge weight filled)
Bro everytime they don't give adj list or adj matrix . They say it is undirected graph and edges will be given then u have to creare and fill adj matrix with two way edges
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.
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
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
Thank you soooooo much!!! Understood!!!!!❤❤
di[i][[j] = Min(d[i][k]+d[k][j]) right ?,u said d[j][k] dont know why
@@sairam3351 min(d[i][k] + d[k][j]) is right..
People say Graph is a difficult Topic, but after going through striver's i haven't faced any problem.so you are a genius.😊
Yes, this is how addiction is built over Algorithms! Thank you Striver :)
Job lgi?
@@anonymousanonymous7507 savage!!
@@anonymousanonymous7507 he's pursuing MTech in CSE from IIT Guwahati. Har jagah cool nahi banna hota, strangers ke saamne cool banne ki naakam koshish karne se achha hai khudpe mehnat karo aur aage badho life me
@@chetanraghavv the guy who ur calling cool is doing Mtech from Harvard . two steps ahead
At 5:39, I think it should be min(d[i][k] + d[k][j])
Yes, a small typo..
Hey, Striver, Pin this comment or write this in ur already pinned comment.
I feel like sitting in a maths class. Amazing explanation! You made a complex algorithm look very simple. Thanks a ton Striver!
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.
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
@@KUMARSAURABH-s5i in case of negative edges followed by an 1e9 edge. this will pose problem. so i think if condition should be proposed
@@KUMARSAURABH-s5i no through we can reduce litte time
I really like the prompt that comes in which a message comes explaining what we should focus on. :)
Yeah, very helpful
Thankyou for the pop-up at 22:42 it gave me relief!
5:46 The equation should be minimum of (d [I] [k] + d [k] [j] ) for calculating for path I => k => j
After watching lots of video , I can only understand this video .
Thank you Striver .❤
thank you so much striver for great explanation. you are such a man who know how teach the students.
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.
devise*
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
Floyd Warshal Algorithm:
1) Initialise dp(N x N) with Infinity.
2) Update dp[i][i] = 0;
3) Update given edge's weight in dp.
4) We need to find the minDistance from i to j via each node.
5) dp[i][j] = dp[i][via] + dp[via][j];
6) As a result, dp will have the min distance from any-to-any nodes of graph.
great
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
Best graph playlist on youtube.
You are the great sir.
Yet another most beautiful explanation on RUclips !!!
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🤩
I can´t say enough, how much i love your videos
Understood! Such a fantastic explanation as always, thank you very much!
Habibi katai bawaal macha rakhe ho ...1 number.chiz hai ye toh
23:14
at this graph at nth itteration
[0][0] via 2 is [0][2] + [2][0] is equal to -5 +2 = -3 which is smaller than zero
hence It confirms negative cycle because [I][I] should be zero
THIS IS REAL THAT SOMETHING WE WANT AND I GURENTEED NO ONE CAN TEACH BETTER THAN THIS EVEN IN PAID COURSES OF LAKHS.
Understood and I too understood your effort which is incredible.
(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
E is V x V-1 is a very very very rare and dense graph..
@@takeUforward Agreed but in interview we are supposed to give worst case time complexity... right? Or am I missing something?
@@ayushrai6699yes you're right don't worry
Can't thank u enough! Striver 🔥
understood! thanks Striver, the explanation is 🔥
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!
Usually you don't get complete graphs always..
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.
@mayankkumar6997: The ELogV for Djikstra's algorithm is Worst Case complexity. It's actual Elog(V^2 ) because in the worst case, the min heap will have V*(V-1) entries in the heap, which approximated to V^2. And that is O(2ElogV), which is O(ElogV). If you repeat that for V vertices, then time complexity is V*O(ElogV) . That outside V cannot be multipled with E.
Another thing to note is that FloydWarshal is always O(V^3)
@@ArdentMusicLover wait why cant the V be multiplied with the E inside
Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
As Striver said always explain why DJ would not work with -ve weights and cycle hence we need to use Floyd Warshal
24:24 :that evil smile @takeUforward😁😂
The voice editing is OP💥
Thank you so much! Awesome explaination!~!
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.
yes
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
@@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
@@CEBMANURBHAVARYA Yeah sorry I miscalculated. Thank you for helping.
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.
Understood sir! thank you so much
understood, thanks for the great explanation
understood just awesome explanation
Awesome Explanation❤❤❤
A very fantastic explanation ❤
Thank you sir 🙏
love u striver...Thanku sooo much
striver understood!!!! thankyou!!!👍
I want to criticize you striver not using the correct infinity symbol.😅
Thank you striver!
2:20 - 16:00
23:00 - 24:02
My favorite algo
u r the true gem🤩
understood, nice video, well explained
Understood bhaiya 🙏❤️
Good explanation
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???
well explained thank you!
Thank you very much. You are a genius.
Awesome. thank you for explanation
Great explanation!
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
void shortest_distance(vector&mat){
int n = mat.size();
for(int via=0; via
Understood 🔥🔥
Understood bhaiya!!
For someone thinking whether can we detetct negative cycle similarly as we detected here by checking the distance[source]
understood 💯
Is it not possible to apply "bellman ford" for all the vertices and store in 2d array for result. ??
amazing explanation *understood*
hats off to you bhaiya
Amazing explanation !
actually if edges is more than V^2/log(v) then the floyd warshall is more optimal then dijkstar algo
what about the conditions where infinity is added to infinity and gives negative result ?
To avoid that we have to if condition like this if(matrix[i][k]!=1e9 and matrix[k][j]!=1e9)
Thank you so much
best.PERIOD.
where is the mathematical proof, that the approach gives the correct ans?
I have a small doubt here, while computing the shortest path by considering node 1 as the intermediary, why are we computing values from that matrix where 0th node is considered as intermediary and not the original matrix? Can anyone help me out with this?
Thanks
understood🔥🔥
understood sir ❤❤
Great Video
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.....
the O(1) you mentioned is space complexity my friend, not time complexity.
Path Printing?
why the code is giving wrong output if we are using INT_MAX instead of 1e9?
Out of bounds
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
Why the code not giving integer overflow in the min function whenever adding with 1e9 plus something
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.
Understood 👍☺️
Understood 🙌💯
Understood ❤❤
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
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
understood brother
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)?
did u get an answer cuz it fails and i dont understand why it fails
5.39,
a small correction,
dis[i][j] = min(dis[i] [k] + dis[k] [j]);
Understood, any problem using this algorithm?
Understood!
Understood Sir
why are you saying...when undirected graph will be given change it to directed by making two edges...it's not already understood because of the adjacency matrix( which already has edge weight filled)
Bro everytime they don't give adj list or adj matrix . They say it is undirected graph and edges will be given then u have to creare and fill adj matrix with two way edges
Ohh thanks
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.
I also have same doubt if you know its answer then please reply
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
why
if == -1 ?
condition not get it
Understood 👍
understood😊😊
Thank you bhaiya
UNDERSTOOD
understood ++, Addicted bruhh with graph playlist, Thanks a lot @raj
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?
Understood✌️
thanks man