G-41. Bellman Ford Algorithm

No video

G-41. Bellman Ford Algorithm

Рет қаралды 199,570

take U forward

Күн бұрын

Пікірлер: 339

@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

@KiranKumar-sb3ti 2 ай бұрын

understood

@KUMARBISHWAJEET-iq6ym 2 ай бұрын

Understood

@sribalajij4386 22 күн бұрын

Understood

@bhagatalisha 14 күн бұрын

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" 😄✨

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

@harshitrautela6585 24 күн бұрын

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

@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

@amanasrani6405 2 ай бұрын

Wahi yr his teachings skills with so much of patiencee

@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 10 ай бұрын

exactly!

@nalingoyal881 5 ай бұрын

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.

@dank7044 Ай бұрын

@@nalingoyal881 Bhai you would find smoller distance for c in the same iteration.

@mandarbhatye17 Жыл бұрын

Thanks

@user-ux1zf3lh1h Ай бұрын

Bhai mrko b bej dai

@EliasEH89 6 ай бұрын

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

@Mercer80 5 ай бұрын

What if graph is disconnected and negative cycle isnt reachable from source then your first point is false.

@shravani2922 2 ай бұрын

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?

@tasneemayham974 2 ай бұрын

@@Mercer80 I think we can apply a quick visited check? Like we did in the first lectures?

@av21015 Жыл бұрын

You explained it really well, If I was to trace this myself I would have sat for an entire day.

@pranshu_awasthi 4 ай бұрын

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.

@tasneemayham974 2 ай бұрын

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_awasthi 2 ай бұрын

@@tasneemayham974 That's what I said. It works for DAG.

@tanyacharanpahadi158 3 ай бұрын

OMG! too much hype about bellman ford algorithm and this is what it is? WOW! you made it so simple. Thanks a ton striver!

@imajt5 7 ай бұрын

Have watched multiple videos, but got the understanding from this explaination. Thanks

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

@LokeshSharma-hm5jz Жыл бұрын

understood, I dont know why i was afraid of this algo in explaining. You made it a butter.

@srinayan390 Жыл бұрын

when u said "yes u r correct", my confidence became infinity❤

@jagannathan1014 10 ай бұрын

Shortly, if N nodes, the node at the farthest level will be at

@tasneemayham974 2 ай бұрын

SUBSCRIBED FROM FIRST RECURSION LIST VIDEO, SIRE!!!! UNDERRRSSTOOODDDD

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

@NeverGive-Up..26 2 ай бұрын

Amazing explanation

@Curiousdev01 Жыл бұрын

Amazing content sir !! ..... if I get a job will be because of you.🙂

@anonymousanonymous7507 8 ай бұрын

Lggyi

@arnabdebnath2425 Жыл бұрын

Bhaiya nind se uth ke breakfast mai apka video khaneka Maza hi kuch Alag h……. Thank you so much bhaiya ….❤

@dhanashreegodase4445 8 ай бұрын

thanks striver, you are the real gem

@naitikrathore3317 Жыл бұрын

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

@rithikraj4316 Ай бұрын

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

@newsbuster2194 11 ай бұрын

Thanks for putting such kind of effort for us.

@ashutoshkumargiri3194 Жыл бұрын

One of the best playlist of Graph on youtube bhaia you deserve more

@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 KZfaq👌

@stith_pragya 8 ай бұрын

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

@keshavprasad1017 3 ай бұрын

thank you so much for the clean and crisp explanation.

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

@alessandrocamilleri1239 Жыл бұрын

Top notch explanation as usual. I would have included an update flag to pre-empt unnecessary iterations.

@amankush2408 2 ай бұрын

Understood. Great explanation for the intuition.

@prateekshrivastava2802 9 ай бұрын

Best explaination of this algo till date !!

@harshith4549 2 ай бұрын

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

@cinime Жыл бұрын

Understood! Super amazing explanation as always, thank you very much!!

@Kparkhade Ай бұрын

Maja aa gaya Itna khatarnak explanation bro 🎉

@bhaktisharma9681 8 ай бұрын

thanks buddy great vid

@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

@user-zn3be9ik1x Жыл бұрын

start the relaxation loop from i=1 to i

@user-fs8km9qc8f Ай бұрын

very nice explanation

@vakhariyajay2224 Жыл бұрын

Thank you very much. You are a genius.

@AyushiPanday12 Жыл бұрын

Thanks Striver for these wonderful lectures. Understood.

@coder6109 3 ай бұрын

Imp when to apply - > when have -ve cycles, idea-> relax all the edges v-1 times , tc->(O(VE))

@mdyousufgazi4030 Жыл бұрын

the thought process is insane

@CodeMode9313 Жыл бұрын

Habibi ye ek number bideo bana di tumne toh ...baut baut danyawaad

@Chirayu19 11 ай бұрын

You got so much energy, bro!

@chitranshkulshrestha485 Ай бұрын

Thanks for the intution

@sdfg204 5 ай бұрын

Had no idea it was this easy, damn. Obviously now that i know the logic, i don't even need to remember it.

@varunakrishnani7688 Жыл бұрын

Understood!! :) Thank you! 🙏🏻😊

@rajeshj4066 Жыл бұрын

@ 16:00 : explained why it has n-1 iterations

@Kokowangmini Жыл бұрын

understood, It was so Awesome.

@virgarg9653 Жыл бұрын

Beautiful Explanation . Loved your content keep going 100%

@kirankuyate6056 Жыл бұрын

greate explaination and with great energy while explaining that make people more creative affracting getting more..💖

@rajatjakhar3146 Жыл бұрын

great explanation 🔥🔥🔥🔥

@lakshyaagrawal2847 Жыл бұрын

bahi kya kar raha h

@kushalkollu8628 4 күн бұрын

striver bhai is goated

@komalkrishna7836 Жыл бұрын

Wow! very well explained, completely Understood

@Stickman-rz9nu 3 ай бұрын

bhaiya , in the for loop terminating condition should be “ i < V “ for n-1 iterations

@sallaklamhayyen9876 3 ай бұрын

great explanation thank you so much and please continue😘😍

@harshalgarg1676 20 күн бұрын

Amazing, thanks a lot.

@harishnaik8164 7 ай бұрын

why adjacent list is not created? why iterate through edges list?

@g51661 10 ай бұрын

Thank you, Striver! Understood

@user-kn1gt7uv3v 2 ай бұрын

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.

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

@kr_ankit123 Жыл бұрын

Understood👍👍 Thanks a lot

@psurya3053 Жыл бұрын

thank you bhaiyya , please can you make a playlist on examples on segment trees from codeforces

@ajitpal0821 Жыл бұрын

5 nodes not edges at 17:24 @take U forward

@aryashjain7893 Жыл бұрын

watching it at 4 a.m. and when u say , I got a better guy, it really hurts :)🤣🤣

@suyashjain3223 6 ай бұрын

Amazing Explanation!!🔥🔥

@smile8510 Жыл бұрын

Master piece !

@ankitpandey7262 Жыл бұрын

Understood !! Amazing as always

@lokeshroy3944 11 ай бұрын

intution was just 🔥🔥🔥🔥🔥🔥🔥🔥

@MojnoSardar Жыл бұрын

Very well explained.

@vyomyadav6497 10 ай бұрын

Good, well explained.

@doingsneakypeakylike Жыл бұрын

Solid explanation man! Thanks!

@soninirav Жыл бұрын

Amazing , very well explained 🔥🔥

@user-up6sl2gq8p 19 күн бұрын

understood too

@herculean6748 Жыл бұрын

lots of love and respect🙌

@Shivanai_h Жыл бұрын

👏 understood...very well explained..

@krishnashah6654 Жыл бұрын

nicely explained, thanks alot

@saniyaverma914 3 ай бұрын

Understood, thank you bhaiya

@manasranjanmahapatra3729 Жыл бұрын

Whatt an explanation amazing. understood.

@UECAshutoshKumar 8 ай бұрын

Thank you sir 🙏

@sanchitdeepsingh9663 Ай бұрын

thanks, understood

@huungryyyy 14 күн бұрын

understood

@vaalarivan_p Жыл бұрын

5:28 - 22:00

@googleit2490 11 ай бұрын

Understood :) Sep'2, 2023 11:38 am

@user-lw9dj8we7k 9 ай бұрын

Understood Sir

@YourITGuy9 Жыл бұрын

at 17.25 Edges are 5 i think u r referring to the no of nodes not edges

@user-tk2vg5jt3l 3 ай бұрын

Thank you bhaiya

@auroshisray9140 Жыл бұрын

Well explained bhai!

@udaytewary3809 Жыл бұрын

Understood bhaiya 🙏❤️

@stark2461 Жыл бұрын

In Case of Negative weight cycles, Dijkstra don't run forever. It produces wrong answer

@nazimhussainmazumder4750 Жыл бұрын

understood very well!

@LearnerForever123 11 ай бұрын

Understood

@gautamsaxena4647 3 ай бұрын

understood bhaiya

@jyothiyadav2595 5 ай бұрын

Just amazing

@juniorboy1903 Жыл бұрын

Understood😉 bhaiya

@bhargavreddy5938 Жыл бұрын

Well explained man ❤️

@gamerjain3795 11 ай бұрын

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 11 ай бұрын

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.