G-41. Bellman Ford Algorithm

GfG-Problem Link: bit.ly/3K7emug
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
---------------------------------------------------------------------------------------------------------------------------

[@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]

understood

[@KUMARBISHWAJEET-iq6ym]

Understood

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

[@nalingoyal881]

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.

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

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

[@srinayan390]

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

[@av21015]

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

[@EliasEH89]

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]

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

[@shravani2922]

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]

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

[@mandarbhatye17]

Thanks

[@imajt5]

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

[@tanyacharanpahadi158]

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

[@cinime]

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

[@ashutoshkumargiri3194]

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

[@AyushiPanday12]

Thanks Striver for these wonderful lectures. Understood.

[@dhanashreegodase4445]

thanks striver, you are the real gem

[@prateekshrivastava2802]

Best explaination of this algo till date !!

[@virgarg9653]

Beautiful Explanation . Loved your content keep going 100%

[@ankitpandey7262]

Understood !! Amazing as always

[@newsbuster2194]

Thanks for putting such kind of effort for us.

[@LokeshSharma-hm5jz]

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

[@keshavprasad1017]

thank you so much for the clean and crisp explanation.

[@Chirayu19]

You got so much energy, bro!

[@komalkrishna7836]

Wow! very well explained, completely Understood

[@soninirav]

Amazing , very well explained 🔥🔥

[@doingsneakypeakylike]

Solid explanation man! Thanks!

[@amankush2408]

Understood. Great explanation for the intuition.

[@varunakrishnani7688]

Understood!! :)
Thank you! 🙏🏻😊

[@tasneemayham974]

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

[@vakhariyajay2224]

Thank you very much. You are a genius.

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

[@herculean6748]

lots of love and respect🙌

[@g51661]

Thank you, Striver!
Understood

[@suyashjain3223]

Amazing Explanation!!🔥🔥

[@Shivanai_h]

👏 understood...very well explained..

[@kr_ankit123]

Understood👍👍
Thanks a lot

[@kirankuyate6056]

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

[@smile8510]

Master piece !

[@stith_pragya]

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

[@manasranjanmahapatra3729]

Whatt an explanation amazing. understood.

[@bhargavreddy5938]

Well explained man ❤️

[@NeverGive-Up..26]

Amazing explanation

[@MojnoSardar]

Very well explained.

[@harshith4549]

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

[@sallaklamhayyen9876]

great explanation thank you so much and please continue😘😍

[@nazimhussainmazumder4750]

understood very well!

[@arnabdebnath2425]

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

[@krishnashah6654]

nicely explained, thanks alot

[@Kokowangmini]

understood, It was so Awesome.

[@alessandrocamilleri1239]

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

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

[@bhaktisharma9681]

thanks buddy great vid

[@saniyaverma914]

Understood, thank you bhaiya

[@vyomyadav6497]

Good, well explained.

[@jagannathan1014]

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

[@mdyousufgazi4030]

the thought process is insane

[@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 CZcams👌

[@auroshisray9140]

Well explained bhai!

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

[@CodeMode9313]

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

[@Curiousdev01]

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

[@anonymousanonymous7507]

Lggyi

[@satyasantoshkumarpadavala4230]

Thank you so much

[@Stickman-rz9nu]

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 🙏❤️

[@parshchoradia9909]

Understood Sir!

[@original_gangsta_]

Understood 🔥🔥

[@sunilpanchal1498]

Understood as always 😃😃

[@jyothiyadav2595]

Just amazing

[@NAYANPATELTECH]

Super explanation😀

[@rajatjakhar3146]

great explanation 🔥🔥🔥🔥

[@lakshyaagrawal2847]

bahi kya kar raha h

[@coder6109]

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

[@aasifali9139]

thx for this video..... Understood.

[@cricketguru7596]

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

[@user-zn3be9ik1x]

start the relaxation loop from i=1 to i

[@UECAshutoshKumar]

Thank you sir 🙏

[@shashankgarg7476]

understood and liked

[@juniorboy1903]

Understood😉 bhaiya

[@lokeshroy3944]

intution was just 🔥🔥🔥🔥🔥🔥🔥🔥

[@psurya3053]

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

[@pranshu_awasthi]

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]

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]

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

[@-VLaharika]

Understood 👍

[@user-lw9dj8we7k]

Understood Sir

[@rajeshj4066]

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

[@sambhavagarwal5871]

understood striver

[@Stickman-rz9nu]

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

[@AshwinNarayananS]

Understood!

[@niharikakumar1533]

Understood sir 🙂

[@selvanambi9852]

Excellent

[@RS-zh1vc]

Thank you...

[@sdfg204]

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

[@kushjoshi9716]

understood!!!!

[@EngineersNeedJobs]

understood!

[@user-kl3qv1sc8k]

amazing🤩😍😍

[@aditya_raj7827]

understood ❤❤

[@aryashjain7893]

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

[@monikagadewar4927]

Just understood 😀

[@kasireddyasam9143]

undershood sir

[@miglaniaakarsh8874]

really nice

[@user-tk2vg5jt3l]

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

[@p38_amankuldeep75]

understood🔥🔥🔥