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
@KiranKumar-sb3ti3 ай бұрын
understood
@KUMARBISHWAJEET-iq6ym3 ай бұрын
Understood
@sribalajij43862 ай бұрын
Understood
@bhagatalishaАй бұрын
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" 😄✨
@aditya-at_its_lowest29 күн бұрын
understood
@harleenkaur7751 Жыл бұрын
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 Жыл бұрын
True , i am also here from a paid course , Someone believes it or not These explanations are way better than in a paid course.
@harshitrautela65852 ай бұрын
@@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)?
@EliasEH897 ай бұрын
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
@Mercer806 ай бұрын
What if graph is disconnected and negative cycle isnt reachable from source then your first point is false.
@shravani29224 ай бұрын
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?
@tasneemayham9744 ай бұрын
@@Mercer80 I think we can apply a quick visited check? Like we did in the first lectures?
@akshaysoni3496 Жыл бұрын
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.
@srimanproductions8396 Жыл бұрын
this should be pinned
@amalkumar256 Жыл бұрын
I did the same thing.
@shivangisehgal Жыл бұрын
exactly!
@nalingoyal8817 ай бұрын
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.
@dank70443 ай бұрын
@@nalingoyal881 Bhai you would find smoller distance for c in the same iteration.
@mashfy6314 Жыл бұрын
This guy got superpower. Can be cast as a Marvel hero "The Explainer" .
@samarthagarwal6965 Жыл бұрын
And we all guys as watchers 😂
@noobcoder6306 Жыл бұрын
nice one
@noobcoder6306 Жыл бұрын
@@samarthagarwal6965 already taken by the "Watcher"
@blutoo1363 Жыл бұрын
I think Striver is already a good enough superhero name
@amanasrani64053 ай бұрын
Wahi yr his teachings skills with so much of patiencee
@mandarbhatye17 Жыл бұрын
Thanks
@VANSHNEGGICS-2022-22 ай бұрын
Bhai mrko b bej dai
@av21015 Жыл бұрын
You explained it really well, If I was to trace this myself I would have sat for an entire day.
@tanyacharanpahadi1584 ай бұрын
OMG! too much hype about bellman ford algorithm and this is what it is? WOW! you made it so simple. Thanks a ton striver!
@GauravThinks Жыл бұрын
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.
@srinayclg390 Жыл бұрын
when u said "yes u r correct", my confidence became infinity❤
@imajt58 ай бұрын
Have watched multiple videos, but got the understanding from this explaination. Thanks
@pranshu_awasthi6 ай бұрын
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.
@tasneemayham9744 ай бұрын
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.
@pranshu_awasthi3 ай бұрын
@@tasneemayham974 That's what I said. It works for DAG.
@jagannathan1014 Жыл бұрын
Shortly, if N nodes, the node at the farthest level will be at
@LokeshSharma-hm5jz Жыл бұрын
understood, I dont know why i was afraid of this algo in explaining. You made it a butter.
@decepticonWave Жыл бұрын
The fact that you explained N-1 is why you are the GOAT. Please make a paid course and we will pay
@ashutoshpandey1639 Жыл бұрын
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.
@ashutoshpandey1639 Жыл бұрын
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 KZbin👌
@Curiousdev01 Жыл бұрын
Amazing content sir !! ..... if I get a job will be because of you.🙂
@anonymousanonymous75079 ай бұрын
Lggyi
@tasneemayham9744 ай бұрын
SUBSCRIBED FROM FIRST RECURSION LIST VIDEO, SIRE!!!! UNDERRRSSTOOODDDD
@dhanashreegodase444510 ай бұрын
thanks striver, you are the real gem
@ashutoshkumargiri3194 Жыл бұрын
One of the best playlist of Graph on youtube bhaia you deserve more
@arnabdebnath24252 жыл бұрын
Bhaiya nind se uth ke breakfast mai apka video khaneka Maza hi kuch Alag h……. Thank you so much bhaiya ….❤
@ayushsharma-bw5ch Жыл бұрын
we need to relax each edge for n - 1 times but in the code we are running loop for
@vishnubanjara5209 Жыл бұрын
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
@shreyanshagrawal3115 Жыл бұрын
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
@newsbuster2194 Жыл бұрын
Thanks for putting such kind of effort for us.
@HarshnitePrasad Жыл бұрын
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.
@keshavprasad10174 ай бұрын
thank you so much for the clean and crisp explanation.
@harshith45493 ай бұрын
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
@naitikrathore33172 жыл бұрын
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!!
@alessandrocamilleri1239 Жыл бұрын
Top notch explanation as usual. I would have included an update flag to pre-empt unnecessary iterations.
@kaichang818624 күн бұрын
understood, thanks for the intuition part
@amankush24083 ай бұрын
Understood. Great explanation for the intuition.
@stith_pragya9 ай бұрын
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@prateekshrivastava280210 ай бұрын
Best explaination of this algo till date !!
@Stickman-rz9nu4 ай бұрын
bhaiya , in the for loop terminating condition should be “ i < V “ for n-1 iterations
@rithikraj43162 ай бұрын
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
@120-venkataraghavareddyvar4 Жыл бұрын
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.
@mdyousufgazi4030 Жыл бұрын
the thought process is insane
@psurya3053 Жыл бұрын
thank you bhaiyya , please can you make a playlist on examples on segment trees from codeforces
@Chirayu19 Жыл бұрын
You got so much energy, bro!
@Kokowangmini Жыл бұрын
understood, It was so Awesome.
@cinime2 жыл бұрын
Understood! Super amazing explanation as always, thank you very much!!
@coder61095 ай бұрын
Imp when to apply - > when have -ve cycles, idea-> relax all the edges v-1 times , tc->(O(VE))
@VrundLeuva-g5s3 ай бұрын
very nice explanation
@rajatjakhar3146 Жыл бұрын
great explanation 🔥🔥🔥🔥
@lakshyaagrawal2847 Жыл бұрын
bahi kya kar raha h
@vakhariyajay2224 Жыл бұрын
Thank you very much. You are a genius.
@chitranshkulshrestha4852 ай бұрын
Thanks for the intution
@AyushiPanday12 Жыл бұрын
Thanks Striver for these wonderful lectures. Understood.
@gamerjain3795 Жыл бұрын
normally we say that dijkstra fails when :- 1. negative cyclic dependency 2. negative weights (not right always) as for a directed graph , if assigning negative weights to an edge , doesn't result in an negative cycle, then you are good to say , your Dijkstra algo. will work there correctly, even with negative edge weight.
@gamerjain3795 Жыл бұрын
so, only thing to consider when choosing between dijkstra and bellman ford is , check for negative cyclic dependencies and not just negative edges. Having negative edges in an undirected graph, which will be converted into directed graph, then definitely dijkstra will fail, bcoz a negative cycle will be formed then.
@varunakrishnani7688 Жыл бұрын
Understood!! :) Thank you! 🙏🏻😊
@user-zn3be9ik1x Жыл бұрын
start the relaxation loop from i=1 to i
@CodeNow-nc4rk18 күн бұрын
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
@smile85102 жыл бұрын
Master piece !
@CodeMode9313 Жыл бұрын
Habibi ye ek number bideo bana di tumne toh ...baut baut danyawaad
@dipendrapratap649514 күн бұрын
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
@virgarg9653 Жыл бұрын
Beautiful Explanation . Loved your content keep going 100%
@sdfg2046 ай бұрын
Had no idea it was this easy, damn. Obviously now that i know the logic, i don't even need to remember it.
@YourITGuy92 жыл бұрын
at 17.25 Edges are 5 i think u r referring to the no of nodes not edges
@kr_ankit123 Жыл бұрын
Understood👍👍 Thanks a lot
@rajeshj4066 Жыл бұрын
@ 16:00 : explained why it has n-1 iterations
@UECAshutoshKumar9 ай бұрын
Thank you sir 🙏
@ajitpal0821 Жыл бұрын
5 nodes not edges at 17:24 @take U forward
@kirankuyate6056 Жыл бұрын
greate explaination and with great energy while explaining that make people more creative affracting getting more..💖
@suyashjain32238 ай бұрын
Amazing Explanation!!🔥🔥
@komalkrishna7836 Жыл бұрын
Wow! very well explained, completely Understood
@harshalgarg16762 ай бұрын
Amazing, thanks a lot.
@saniyaverma9145 ай бұрын
Understood, thank you bhaiya
@sallaklamhayyen98764 ай бұрын
great explanation thank you so much and please continue😘😍
@kasamadhu3509 Жыл бұрын
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.
@akashkumarsingh8369 Жыл бұрын
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.
@lakshsinghania Жыл бұрын
@@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
@lakshsinghania Жыл бұрын
@@akashkumarsingh8369 koi aur tc lo and then check
@dhruvgupta3879 Жыл бұрын
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.
@jiyabhagat65108 ай бұрын
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
@UtpalPodder-b4r3 ай бұрын
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.
@herculean6748 Жыл бұрын
lots of love and respect🙌
@Kparkhade2 ай бұрын
Maja aa gaya Itna khatarnak explanation bro 🎉
@g51661 Жыл бұрын
Thank you, Striver! Understood
@harishnaik81648 ай бұрын
why adjacent list is not created? why iterate through edges list?
@vyomyadav649711 ай бұрын
Good, well explained.
@MojnoSardar Жыл бұрын
Very well explained.
@ankitpandey72622 жыл бұрын
Understood !! Amazing as always
@aryashjain78932 жыл бұрын
watching it at 4 a.m. and when u say , I got a better guy, it really hurts :)🤣🤣
@auroshisray9140 Жыл бұрын
Well explained bhai!
@stark2461 Жыл бұрын
In Case of Negative weight cycles, Dijkstra don't run forever. It produces wrong answer
@redgreenblue_rgb Жыл бұрын
Understood!!! After striver Explanation my reaction So easy
@Alwaysalearner123 Жыл бұрын
In for loop i
@divyareddy762213 сағат бұрын
takeaway: having n-1 iterations, helps bellman ford to avoid infinite loop. It won't again try to find a better distance.
@NAYANPATELTECH10 ай бұрын
Super explanation😀
@krishnashah6654 Жыл бұрын
nicely explained, thanks alot
@lokeshroy3944 Жыл бұрын
intution was just 🔥🔥🔥🔥🔥🔥🔥🔥
@Stickman-rz9nu4 ай бұрын
bhaiya , i want to thank you for this playlist, yesterday i attempted a codechef contest and there was a question related to graph and i solved it correctly using dijkstra, though i got a TLE 💀 but the code was correct. it was my first graph question on codechef. thank you so much 🥳🥳
@udaytewary3809 Жыл бұрын
Understood bhaiya 🙏❤️
@doingsneakypeakylike2 жыл бұрын
Solid explanation man! Thanks!
@Shivanai_h2 жыл бұрын
👏 understood...very well explained..
@vaalarivan_p Жыл бұрын
5:28 - 22:00
@soninirav2 жыл бұрын
Amazing , very well explained 🔥🔥
@sanchitdeepsingh96633 ай бұрын
thanks, understood
@manasranjanmahapatra37292 жыл бұрын
Whatt an explanation amazing. understood.
@satyasantoshkumarpadavala42307 ай бұрын
Thank you so much
@bhargavreddy5938 Жыл бұрын
Well explained man ❤️
@original_gangsta_ Жыл бұрын
Understood 🔥🔥
@kushalkollu8628Ай бұрын
striver bhai is goated
@nazimhussainmazumder4750 Жыл бұрын
understood very well!
@juniorboy19032 жыл бұрын
Understood😉 bhaiya
@asktostranger82962 жыл бұрын
Bahi abhi graph ki kitni video he Aur bachi He Big fan 😍🙏