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
Thanks Striver. Trust me, even in my paid course, they just simply explained the working of Dijkstra and Bellman without going into such detail. U r the best teacher.
@@dharmvir2330 So why did you take the paid course? Is there any advantage you can think of that the paid course is giving better than Striver(just curious to know)?
Thank u. Note: The Dijkstra's algorithm implemented in G-32 can handle any negative edges graph EXCEPT the following cases: 1- Directed graph having any negative cycle (cycle with sum < 0) 2- Undirected graph having any negative edge because the edge in undirected graph is by itself a cycle
Your thought is right, my doubt is why not follow Dijkstras algorithm implemented in G-32 for directed graphs with no negative cycles. The time complexity is even less than Bellmanford algorithm. What is the use of Bellman ford algorithm?
Improve Time Complexity by exponential with just minor observation: Put int count =0; After the first loop & increment the value of count by 1 when the dist array will get updated and at the end of the second loop, if the value of count is not increased then directly return dist array. if no update in dist array happened that means we already calculate dist array, no need to do further iteration, In the worst case it does not have any impact, but for rest, it decreases TC a lot. It Reduce the number of iteration in Best & Average cases.
Is this case even possible? in a graph like this : a-> b-> c . if we have found smaller distance for a->b , we will surely find shorter distance for b->c in next iteration. Let me know if you think differently.
Question: why do we need N-1 iterations? Reason: Because we first of all set the source distance out ot all the N edges, now we have N-1 edges, to fill their distances w.r.t source, we need at max N-1 iterations for each Node.
2 din baad DAA ki paper hai and Bellman Ford aayega exam me, soch hi rha tha ki striver agr next video yhi upload kr de fir to mjaa hi aa jaye and aaj subh dekha BOOM!!
Things i figured out : 1. If you know a path to reach a node you can figure out the paths to reach nodes adjacent to it. 2. why repeat n-1 times, every time you run through the edges you find a path to reach the node and the cost to reach it, if its better you update, incase the cost doesnt update you have been able to exhaust the minimum cost path.
23:34 - If someone is wondering like me as to why the edges are passed by reference using & If you don't use a reference, the function would create a copy of the edges vector every time the function is called, which can be very costly in terms of memory and time, especially for large graphs
We can also fit the negetive cycle check in the for loop with extending its range to V and checking if its the Vth iteration in relaxtion without writing repeated code. Also the best and worst cases can be improved by keeping a count of how many relaxations done in each iteration which signifies that if at any point no relaxation can be done then no further iteration is required bcoz there will be no change in distances further. Here's how its done: vector bellman_ford(int V, vector& edges, int S) { vector dist(V, 1e8); dist[S] = 0; for(int i = 1; i
one thing should also be mentioned that if a graph on N nodes have cycle, then their is path exist having more than N - 1 edges from first to last node. By the way best explanation on UA-cam👌
Dijsktra's code which striver has taught works for negative edges , it just not works for Negative edge cycles. So all in all , it would work for DAG with positive / negative weights.
Of course, because Dijkstra doesn't work for negative edges in UNdirected grapsh: What if you have 0 - 1 with -1 weight? It will give TLE. But in directed, 0->1 with -1, 1 can never go back to 0 so the loop will not work.
I guess for the question why we need to do n-1 relaxations to each node is that ,, suppose we have 3 nodes directly connected a node and we have relaxed those nodes,, now in typical dijkstra algo,, the node with smallest value of relaxation will never get relaxed again, but if there are negative weights,, then there is a chance that the the node with smallest value of relaxation will get relaxed again. Since each node at max gets connected to n-1 nodes, so thus n-1 relaxations.
I just wanted to play around with dijkstra and I know this in not an optimal solution and thought of doing the negative cycle part with dijsktra only. My thought process is very simple with djkstra also you could solve the problem the only issue was negative cycle. Now a cycle in itself is not an issue but a cycle with reducing distance does. According to the condition of dijkstra it would enter the if block if we get a decreasing distance and this will only happen in negative cycle or in linear path. To check that we can store paths for each node. Next time we visit that node we check do we already have the node itself in the path that means we are in a cycle or else there is a different path that led us to the node. Code: vector bellman_ford(int V, vector& edges, int S) { // Code here vector adj(V); for(int i=0;i
Presense of negative edge does not always result incorrect result ...that could be easily proved in the second example if there is a path say from 4 to 3 with -1 edge weight ....but if the negative edge cycle change the previous path length which we got after n-1 iteration then it cause problem.
If we will take nodes in a increasing order then that time I think we can find the distance in 2-3 iteration as well we don't need to do n-1 iterations
striver: Directed Acyclic Graph with negative edges we can use Dijkstra's right? Example: vertices 3, edge 3 node node weight; 0 1 10 1 2 -8 0 2 5 source 0 ; it is giving 0, 10, 2 correct, bellman ford is used for only detecting negative cycles that can't be done using dijkstra's as you explained in series.
same confusion hai bhai. smjh nhi aa rha agar cycle nhi hua aur negative weight hai to dijkstra glt ans dega ya shi. Dry run krne pr shi hi aa rha hai.
@@akashkumarsingh8369 it shouldn't work as per the real meaning of dijkstra's whether its 1. having neg weights 2. having neg cycle becoz this already includes negative weight in the path
Yes, Dijkstra can be used for Directed Acyclic Graph with negative weights. Since it doesn't have a negative cycle, it will not get caught in an infinite loop
I have a question: the only reason we do N-1 iterations is because the node might be ordered from end to beginning with the source at the end and its connected node after. What if we re-write the graph such that the first edge is always the source and so on.. till the end? Will that need N-1 iterations now?
I had this small question, we dont have exact infinity in implemntation so, suppose we have 1e9, then at some condition of negative edge weight 1e9-2 > 1e9 would we true?
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
understood
Understood
Understood
Striver you are amazing, you need to worry, your supporters will keep on increasing, infact next gen of engineers will be brought up "only by you" 😄✨
understood
Thanks
Bhai mrko b bej dai
Thanks Striver. Trust me, even in my paid course, they just simply explained the working of Dijkstra and Bellman without going into such detail. U r the best teacher.
True , i am also here from a paid course , Someone believes it or not These explanations are way better than in a paid course.
@@dharmvir2330 So why did you take the paid course? Is there any advantage you can think of that the paid course is giving better than Striver(just curious to know)?
Thank u.
Note: The Dijkstra's algorithm implemented in G-32 can handle any negative edges graph EXCEPT the following cases:
1- Directed graph having any negative cycle (cycle with sum < 0)
2- Undirected graph having any negative edge because the edge in undirected graph is by itself a cycle
What if graph is disconnected and negative cycle isnt reachable from source then your first point is false.
Your thought is right, my doubt is why not follow Dijkstras algorithm implemented in G-32 for directed graphs with no negative cycles. The time complexity is even less than Bellmanford algorithm. What is the use of Bellman ford algorithm?
@@Mercer80 I think we can apply a quick visited check? Like we did in the first lectures?
After many years I finally understood with your example why bellman ford runs for (n - 1) iterations. Thank you
Improve Time Complexity by exponential with just minor observation:
Put int count =0; After the first loop & increment the value of count by 1 when the dist array will get updated and at the end of the second loop, if the value of count is not increased then directly return dist array. if no update in dist array happened that means we already calculate dist array, no need to do further iteration, In the worst case it does not have any impact, but for rest, it decreases TC a lot. It Reduce the number of iteration in Best & Average cases.
this should be pinned
I did the same thing.
exactly!
Is this case even possible? in a graph like this : a-> b-> c . if we have found smaller distance for a->b , we will surely find shorter distance for b->c in next iteration. Let me know if you think differently.
@@nalingoyal881 Bhai you would find smoller distance for c in the same iteration.
You explained it really well, If I was to trace this myself I would have sat for an entire day.
This guy got superpower. Can be cast as a Marvel hero "The Explainer" .
And we all guys as watchers 😂
nice one
@@samarthagarwal6965 already taken by the "Watcher"
I think Striver is already a good enough superhero name
Wahi yr his teachings skills with so much of patiencee
OMG! too much hype about bellman ford algorithm and this is what it is? WOW! you made it so simple. Thanks a ton striver!
Question: why do we need N-1 iterations?
Reason: Because we first of all set the source distance out ot all the N edges, now we have N-1 edges, to fill their distances w.r.t source, we need at max N-1 iterations for each Node.
Have watched multiple videos, but got the understanding from this explaination. Thanks
when u said "yes u r correct", my confidence became infinity❤
understood, I dont know why i was afraid of this algo in explaining. You made it a butter.
Bhaiya nind se uth ke breakfast mai apka video khaneka Maza hi kuch Alag h…….
Thank you so much bhaiya ….❤
Shortly, if N nodes, the node at the farthest level will be at
One of the best playlist of Graph on youtube bhaia you deserve more
2 din baad DAA ki paper hai and Bellman Ford aayega exam me, soch hi rha tha ki striver agr next video yhi upload kr de fir to mjaa hi aa jaye and aaj subh dekha BOOM!!
Things i figured out :
1. If you know a path to reach a node you can figure out the paths to reach nodes adjacent to it.
2. why repeat n-1 times, every time you run through the edges you find a path to reach the node and the cost to reach it, if its better you update, incase the cost doesnt update you have been able to exhaust the minimum cost path.
SUBSCRIBED FROM FIRST RECURSION LIST VIDEO, SIRE!!!! UNDERRRSSTOOODDDD
23:34 -
If someone is wondering like me as to why the edges are passed by reference using &
If you don't use a reference, the function would create a copy of the edges vector every time the function is called, which can be very costly in terms of memory and time, especially for large graphs
thanks striver, you are the real gem
We can also fit the negetive cycle check in the for loop with extending its range to V and checking if its the Vth iteration in relaxtion without writing repeated code. Also the best and worst cases can be improved by keeping a count of how many relaxations done in each iteration which signifies that if at any point no relaxation can be done then no further iteration is required bcoz there will be no change in distances further. Here's how its done:
vector bellman_ford(int V, vector& edges, int S) {
vector dist(V, 1e8);
dist[S] = 0;
for(int i = 1; i
one thing should also be mentioned that if a graph on N nodes have cycle, then their is path exist having more than N - 1 edges from first to last node.
By the way best explanation on UA-cam👌
Best explaination of this algo till date !!
Dijsktra's code which striver has taught works for negative edges , it just not works for Negative edge cycles. So all in all , it would work for DAG with positive / negative weights.
Of course, because Dijkstra doesn't work for negative edges in UNdirected grapsh: What if you have 0 - 1 with -1 weight? It will give TLE. But in directed, 0->1 with -1, 1 can never go back to 0 so the loop will not work.
@@tasneemayham974 That's what I said. It works for DAG.
Thanks for putting such kind of effort for us.
we need to relax each edge for n - 1 times but in the code we are running loop for
if we assume it 0 index based then V-2 is right and if we take it 1 based than simply run it for 1 less as V-1
for(int i = 0; i < N; i++) : runs for N times ( 0 to N-1)
for(int i = 0; i < N-1; i++) : runs for N-1 times ( 0 to N-2) - which is required
thank you so much for the clean and crisp explanation.
The fact that you explained N-1 is why you are the GOAT. Please make a paid course and we will pay
But the one thing should also be mentioned that if a graph on N nodes have cycle then their is path exist having edges more than N - 1.
Amazing content sir !! ..... if I get a job will be because of you.🙂
Lggyi
Imp when to apply - > when have -ve cycles, idea-> relax all the edges v-1 times , tc->(O(VE))
5 nodes not edges at 17:24 @take U forward
understood, It was so Awesome.
You got so much energy, bro!
Thanks Striver for these wonderful lectures. Understood.
Top notch explanation as usual. I would have included an update flag to pre-empt unnecessary iterations.
@ 16:00 : explained why it has n-1 iterations
Understood. Great explanation for the intuition.
the thought process is insane
Understood! Super amazing explanation as always, thank you very much!!
start the relaxation loop from i=1 to i
Habibi ye ek number bideo bana di tumne toh ...baut baut danyawaad
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I guess for the question why we need to do n-1 relaxations to each node is that ,, suppose we have 3 nodes directly connected a node and we have relaxed those nodes,, now in typical dijkstra algo,, the node with smallest value of relaxation will never get relaxed again, but if there are negative weights,, then there is a chance that the the node with smallest value of relaxation will get relaxed again. Since each node at max gets connected to n-1 nodes, so thus n-1 relaxations.
Simple in every cycle worst can be 1 updation, so we need to update n - 1 updation as we already have 0 or src updated manually
bhaiya , in the for loop terminating condition should be “ i < V “ for n-1 iterations
takeaway: having n-1 iterations, helps bellman ford to avoid infinite loop. It won't again try to find a better distance.
Beautiful Explanation . Loved your content keep going 100%
Maja aa gaya
Itna khatarnak explanation bro 🎉
I just wanted to play around with dijkstra and I know this in not an optimal solution and thought of doing the negative cycle part with dijsktra only. My thought process is very simple with djkstra also you could solve the problem the only issue was negative cycle. Now a cycle in itself is not an issue but a cycle with reducing distance does. According to the condition of dijkstra it would enter the if block if we get a decreasing distance and this will only happen in negative cycle or in linear path. To check that we can store paths for each node. Next time we visit that node we check do we already have the node itself in the path that means we are in a cycle or else there is a different path that led us to the node.
Code:
vector bellman_ford(int V, vector& edges, int S) {
// Code here
vector adj(V);
for(int i=0;i
Presense of negative edge does not always result incorrect result ...that could be easily proved in the second example if there is a path say from 4 to 3 with -1 edge weight ....but if the negative edge cycle change the previous path length which we got after n-1 iteration then it cause problem.
If we will take nodes in a increasing order then that time I think we can find the distance in 2-3 iteration as well we don't need to do n-1 iterations
Wow! very well explained, completely Understood
understood, thanks for the intuition part
20:11 activated SUPER SONIC MODE 🔥
Had no idea it was this easy, damn. Obviously now that i know the logic, i don't even need to remember it.
Thank you, Striver!
Understood
Thank you very much. You are a genius.
In for loop i
intution was just 🔥🔥🔥🔥🔥🔥🔥🔥
great explanation 🔥🔥🔥🔥
bahi kya kar raha h
Understood bhaiya 🙏❤️
Understood !! Amazing as always
Amazing Explanation!!🔥🔥
Understood!! :)
Thank you! 🙏🏻😊
baad m distance array ka sum nikal k check kr skte h n negative cycle ka
for(int i=0;i
thank you bhaiyya , please can you make a playlist on examples on segment trees from codeforces
In Case of Negative weight cycles, Dijkstra don't run forever. It produces wrong answer
at 17.25 Edges are 5 i think u r referring to the no of nodes not edges
striver: Directed Acyclic Graph with negative edges we can use Dijkstra's right?
Example: vertices 3, edge 3
node node weight;
0 1 10
1 2 -8
0 2 5
source 0 ;
it is giving 0, 10, 2 correct, bellman ford is used for only detecting negative cycles that can't be done using dijkstra's as you explained in series.
same confusion hai bhai. smjh nhi aa rha agar cycle nhi hua aur negative weight hai to dijkstra glt ans dega ya shi. Dry run krne pr shi hi aa rha hai.
@@akashkumarsingh8369 it shouldn't work as per the real meaning of dijkstra's whether its
1. having neg weights
2. having neg cycle becoz this already includes negative weight in the path
@@akashkumarsingh8369 koi aur tc lo and then check
it won't work with dijkstra. We mark a node as visited in dijkstra and do not visit it again, which should not be done in case of negative weights.
Yes, Dijkstra can be used for Directed Acyclic Graph with negative weights. Since it doesn't have a negative cycle, it will not get caught in an infinite loop
striver bhai is goated
Solid explanation man! Thanks!
lots of love and respect🙌
Amazing , very well explained 🔥🔥
Understood, thank you bhaiya
Master piece !
watching it at 4 a.m. and when u say , I got a better guy, it really hurts :)🤣🤣
Understood😉 bhaiya
Good, well explained.
26:08 its cubic not quadratic
Understood👍👍
Thanks a lot
very nice explanation
Thank you sir 🙏
Very well explained.
5:28 - 22:00
Thanks for the intution
Well explained bhai!
can we consider the no of iterations as maximum path length from source?
what if we sort the given input such that the src node is at the start and so on......will we be able to to compute it all in just 1 relaxation then?
Super explanation😀
tq striver bhaiyya
I have a question: the only reason we do N-1 iterations is because the node might be ordered from end to beginning with the source at the end and its connected node after. What if we re-write the graph such that the first edge is always the source and so on.. till the end? Will that need N-1 iterations now?
I had this small question, we dont have exact infinity in implemntation so, suppose we have 1e9, then at some condition of negative edge weight 1e9-2 > 1e9 would we true?
Amazing, thanks a lot.
He is Godfather ❤❤❤❤❤❤❤❤❤❤❤❤❤❤🎉🎉🎉🎉🎉🎉❤❤❤❤❤
nicely explained, thanks alot
greate explaination and with great energy while explaining that make people more creative affracting getting more..💖
Well explained man ❤️
Understood 🔥🔥