4.1 MultiStage Graph - Dynamic Programming

Multistage Graph Problem
Solved using Dynamic Programming
Forward Method
PATREON : www.patreon.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...

[@marykapodistria7204]

the best videos on DP. You have a great charisma. Thank you for all your videos.

[@ABRAHAMMENGISTU-A1M]

Hi

[@gurashishanand3082]

Sir, may you have the most wonderful life ahead. We need more professors like you.

[@kinglygaurav]

The reason the books are messed up and so confusing is because they start at the formula that you described at 16:47 haha. Thank you for your patient teaching sir. You rock!

[@shashanksagarjha2807]

please watch this playlist for detailed explanation of dynamic programming..kzbin.info/aero/PLeF0b8iqbx4mTBJZ5ukIYj92_B4k2L1-8..

[@RizzyClipz]

@@shashanksagarjha2807 uour link doesn't work

[@shashanksagarjha2807]

@@RizzyClipz Please check this: kzbin.info/aero/PLeF0b8iqbx4mTBJZ5ukIYj92_B4k2L1-8

[@N-e0N]

@Luka Karsyn @Enoch Kobe STFU BOTS.

[@sachinfulsunge9977]

He teleported at 16:44

[@reyvanadryan2513]

I've got my degree, because of people like you sir! Thanks a lot!

[@thomasdante9309]

Probably the clearest explanation on Multi Stage Graphs out there. Much easier to understand than ones that use too much technical jargon.

[@shambhaviojha92]

Sir your explanation was very simple, to the point and easy to learn. Thank you for making dynamic programming easy and fun😀

[@Abin_oommen]

Cool

[@aamgaming1238]

😊😮

[@eugeniaancilla351]

Your explanation on the topic of multistage graph really helps me understand the topic better. I really like your approach to explaining the topic, where you explain the topic using an example first, then give the formula afterward. This helps me understand the concept instead of just following a formula. Your explanation makes this complicated topic look so simple, thank you for your clear explanation!

[@davithov]

I think you should start teaching teachers how to teach.

[@rajime1645]

Nowadays teachers are working hard but students are not showing their interest

[@ChandanGowda-f1x]

I guess ur teacher​@@rajime1645

[@kanishqsoni]

Teachers are already studying by him

[@shrikantdamale1859]

He is

[@jimmylander2089]

Algorithms is such an interesting subject to explore. It disappoints me greatly how little passion my lecturers seem to have for teaching it. During the corona virus lockdown they abandoned us students (they did not organize any online activity or chat) and did not provide us with any materials to study from or upload any videos (all we had were the presentations which naturally had little to no information in them). Not that they were very good teachers in the first place. Regardless, thank you for these wonderful videos!

[@rheinokatili8120]

Another excellent video. It's really amazing how you can explain the process of solving multistage graphs with ease. The way it uses dynamic programming as the forward technique to solve the problem has got to be my favourite.

[@avinashshankarbharadwaj6064]

This is possibly the best video to watch and understand multistage graphs. Thank you so much!

[@devanshusachdev9190]

Sir your way of explaining methods is too good.... I have to cover the whole syllabus of daa within 2 weeks and following your lectures,I think i can do it.... Thank u soo much sir for putting so much efforts for us....

[@almostnoob6986]

I have my exam tomorrow... and here I am

[@manojramesh4598]

@@almostnoob6986 so am i

[@yz1938]

How much do I wish you were my algorithm professor...you explain things in such a clear and precise manner. It is an art

[@kadelchess42]

Many of the cuts are horrendous, but you make absolutely up for it by being splendid! Thanks a lot sir for the great, clear explanations.

[@vincentl94]

The explaination is very clear, the textbook formula makes it really confusing, but the way you explain it makes the formula make sense.

[@ambatikalyani2317]

The way he teaches is outof the box

[@swathivenkatesh465]

Superb sir..you have taught the multistage graph very easily..Thank you

[@nathanraditya7288]

This video cleared up the couple of things I had a hard time understanding. Your explanations are very easy to understand.

[@chinmaydas4053]

Sir you are awesome, great, explain actual algorithm problems.. actually helpful..

[@TheKevin12343]

One of the best explanation available on internet.

[@MrWorld-4]

I don't have such a beautiful words to introduce the beauty of your teaching I love you my respected sir ❤️❤️❤️

[@eliasq11421]

Thanks to you and your videos I was able to approve Programming 3! I'm glad of finding your channel on KZbin.

[@y.so.sarthak]

sir u donno but ye videos humm jaise students li life changing hoti hai

[@sharathnagendran3754]

Abdul guru ji. You are the best teacher that I have seen so far.

[@alica5796]

Thank you for the clear explaination on Multistage Graph sir Abdul! This helps me to understand the topic a lot better, especially on the part where you show us the example first and then the formula. It’s very detailed yet its not making the topic becomes complicated, instead, it becomes simpler. Thank you sir!

[@ridhishjain8886]

me kafi time se dhoondh rha google, YT pr graph modelling kya cheej h, GS coding round me aai thi cost and graphs related.............. finally ye video mili.....and dil ko sukoon bhi

[@santoshbehara2589]

Peaceful explanation 😃

[@Danish-saifi1]

By peaceful community

[@vallurideepak3677]

sir we are expecting network flow algorithm for you hopefully we would be waiting for it, most of the students from our collage were following your lectures and your teaching is simply awesome

[@huajinqu7883]

you explained the complex concept so easily. a lot of respects Sir

[@SamJam-24]

DAA Ki devudu sir meru 🙏🙏

[@akhilhenry1844]

Nijame

[@sheharyardawar4463]

wow

[@devanlucian1598]

This video is very helpful, Although at first i was intimidated by the graph, at the end of the video I understand how to solve a problem like this. I liked how after the example, you gave the equation and explained clearly what the symbols are, which was very easy to understand since you started with the example first, hence not intimidating people with a sudden equation that they may or may not know where it came from. Thank you for the great explanation sir.

[@anshuprakash5022]

Wow... Amazing crystal cleared sir, huge respect.. 🙏🙏🙏🙏

[@rohittechlife6415]

Best teacher than our school professor

[@bobitttt]

Thank you for your detailed explanation; it helped me understand the process.

[@esther.vemberly]

Thank you sir for the clear explanation, Sir! I like how you gave the formula after you had explained the steps with the graph and table, instead of giving it right away at the start. I also understand better how dynamic programming works in this multistage graph because you emphasized it at the end.

[@AnitShrestha]

I was finding it hard to visualize any problem in terms of Dynamic Programming technique as I was not able see how a problem 1. has an optimal substructure 2. has overlapping subproblems that are two criteria for a problem to identify that it could solved through dynamic programming. This presentation indeed has added a lot of value in terms of clarifying some of my confusions. The description of the function to find the optimum solution in the end of the video has been a lot of help as I could read a lot of such statement in many other sources but was not able to relate them overall in my thinking or analysis of the problem solving process. Explanation is of the highest quality, being clean and precise. Thank you very much!

[@AnitShrestha]

@@abdul_bari I have already done that Sir. Thank you. I am just looking at your comments on the notification and replying to ones I can find. Thank you again.

[@ashishkumaryadav5252]

Sir greedy work karti to hai, hum nodes ko min heap me store karte hai aur kisi bhi node ka distance tabhi finalise hota hai jab hum use min heap se pop karle, jaise first time distance 25 aaya to vo final thodi hua hai hum aur nodes ko min heap se pop karenge or check karenge ki isse better option hai kya, similar to dijkstra to isse time complexity better hi aaegi in comparison to (V^2). Do you agree?

[@asterynn941]

you always give clear explanation, the topics in your videos are easy to understand. and i appreciate you drawing the graphs since it's super helpful

[@justinevan9750]

Thank you so much for the lecture sir, your videos are really helpful especially because you give detailed and easy to follow explanations. My favorite part is when you explain about the shortest path with forward method vertex by vertex. It helps a lot!

[@seanwijaya2404]

Thank you sir for the clear explanation. Because of this video I now understand better about dynamic programming and multistage graph specifically. I really like how you explained it by walking us through all the steps with simple examples which makes it easy to understand.

[@raymondp2809]

Very clear and concise explanation as always. Made me really understand more about how to obtain the formula with the way you teach. Thanks.

[@nathanjlee5247]

Thank you sir! A very elegant demonstration of Dynamic Programming and path storing. It was also very cool how you derived the formula from the process you already did, makes it so much more intuitive than just a bunch of fancy letters. Math would've been so much easier if it followed this teaching style :P

[@shawnyasha7715]

Thank you, sir. Your explanation is really clear about the multistage graph where you teach from the basics of how to do the table, the formula, and the sequence of decisions because it is needed in dynamic programming .

[@avenger1898]

Really helpful sir ,No one teaches like you sir .

[@timothyliundi1893]

Thank you so much sir. I'm confused at first on what is "c( )" and the difference with "cost( )". But then at 14:39 you explained it and it cleared the confusion. I like how after the tough finding each and every minimum path on each vertex, using "d( )" you can easily trace the minimum path. Your explanation is very easy to understand. What a take up and way to express!

[@SRNR_PODCAST.]

a gold mine in KZbin.

[@shubhambatham49]

I have seen people in the comment section mentioning other ways to solve the problem.With an attempt to further clarification.I have attempted filling the table from the source and got exactly the same result.And to those mentioning that it is easier using Dijkstra, I agree, but Dijkstra is going to take slightly more time considering the additional updations required for each node, oterwise it is just fine.

[@aubreysitepu5249]

The video provide a very clear explanation about the problem and solution. Every minute I spend watching is very insightful. Thank you for making this video sir!

[@ShubhamYadav-eq8gs]

Your teaching methodology is really good....

[@blekekok]

Thank you sir for this. Your teachings are always straightforward and understandable :)

[@spartaninfo3273]

sir, ur explanation is rod.you r making simple problem into complex with your way of explanation.

[@jason-yb9qk]

The explanation is very easy to understand. Very helpful video for a computer science student like me. Thanks a lot sir!

[@cs_39_sharma_priyansh75]

Sir very very veryyyyy good explanation thank you sir you are life saver no one can explain better than you

[@tutuStillLearning]

That's sooo clear! Thank you sir and thank you for all your videos!

[@egidiusvico9313]

Thanks for the lecture on the multistage graph topic. your videos are always clear and easily understandable and the examples you provide helps me understand the topic even furhter

[@carlac1482]

Your video is very helpful, sir! it's clear and simple. The explanation for each steps are very detailed and it's easy for me to understand, thank you sir.

[@waifuhunter9815]

Thank you for the explanation method. It make a complex explanation easier

[@hadisurya09]

Thank you for this sir, your teaching is straightforward and easy to understand.

[@scholli99]

you explain this by far better than this MIT guy. Thank you sir. Adblock off only here :)

[@Artaxerxes.]

but G2 got fucked by LPL

[@pattrickritter2706]

great explanation as always sir, I really like when you explain it while giving us examples so we can understand it better 👍

[@jeffrbe]

A very good explanation sir. I like how simple you explain the steps to get the formula.

[@TarangaDatta]

Amazing explanation Sir...needed to cover this portion and a few others for my upcoming exam at IIM Calcutta. You made sure I'll never forget these concepts in this lifetime!

[@booleangray2225]

Small correction in the formula: cost(i, j) = min{ cost(i, j), c(j, l) + c(i + 1, l)} And the array would have been initialized with Integer.MAX_VALUE.

[@vijayreddy7585]

You are great tutor for beginners Now I am clear with the algorithm concept

[@katrielwidjaja2839]

Thank you, sir, for the explanation. I really like your explanation it was very simple and straightforward. It helped me understand this topic better.

[@tanishkaachaturvedi2173]

Just no words for the great explanation. Thank you very much 🙏

[@subramaniyanvg6367]

Best teacher anyone can get.

[@ashar5511]

First I thing this program is very difficult to understand , after I saw ur lecture i can solve the problem

[@sheelstera]

Hello @Abdul Bari, Thank you so much for the video. I am having slight trouble trying to understand the "decision making" nature of dynamic programming here. The problem here has been divided into two phases. Phase 1 - fills up the cost and distance data structure and bears a striking similarity to Dijkstra's where we find the vertex with the shortest path to the preceding stage starting from the sink Phase 2 - uses the populated data structure from Phase 1 to trace its way back from the source to sink. My questions are: i. I am trying to make the most of the individual points you mentioned about Dynamic Programming: (a) memoization/tabulation and (b) decision making at each stage. In this particular case, Phase 1 seems to be doing the tabulation part where you fill in the data structure to use it later in Phase 2. And as you said in the video, the decision making part happens in the second Phase: the Forward method. Please correct me if I am wrong. If my understanding is right then, this leads me into the second question. ii. Where is the decision making happening in Phase 2 considering the data structure from Phase 1 has already given you the path or at least the vertex to be chosen at each stage and we are just using the one and only obvious vertex at each stage as populated in the data structure from Phase 1 to trace back to the sink starting from the vertex! Request your thoughts.

[@sheelstera]

Alright.. Sorry about that The problem here has been divided into two phases. Phase 1 - fills up the "cost and distance" data structure (tabulation) Phase 2 - uses the populated data structure from Phase 1 to make decisions to trace its way back from the source to sink and we call that forward method My question is: where really is the "dynamic" decision making happening considering the data structure has already given you the vertex to be chosen at each stage and we are just using the entry as populated in the data structure to trace back to the sink starting from the source?

[@sheelstera]

@@abdul_bari Alright thank you so much

[@sudaminis1302]

Your videos are priceless! Much gratitude!

[@Emma-ud9xm]

Thank you so much..It is very helpful... is this method applicable to other directed weighed graphs such that vertex 1 is directly linked to vertex 6 for example (stage 1 to stage 3)? if i want to use the dynamic programming strategy to solve the shortest path problem for a given graph... is that all the problem can be presented as multistage (example of graph your video 3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy method) Otherwise what is the best algorithm using DP to solve single sorce shortet path?

[@deepanshsharma7354]

Please make a video professor on the proof of optimality that this dynamic approach guarantees an optimal solution

[@havetocheckhavetocheck1761]

still the best tut among other KZbinr explanations

[@ms_admires]

extremely crisp and clear. very easy approach. Thank you so much..

[@sriseenu5937]

Thank you sir..it's very useful & I understand clearly..way of ur teaching is very nice

[@369media]

am from Ethiopia thanks so much

[@Voice1804]

The best teacher, thank you sir

[@chaithu_art_world5076]

Every time I got a doubt my mind simply tells me watch abdulbari channel "Tq sir "

[@mariazeb5145]

How do we find the cost. If I find through graph it gives different value and if I find it through table it gives different.

[@bharaths3075]

Sir! Why cant we solve this using greedy method?.We can use Dijkstra's shortest path right?

[@rajavarma1227]

Sir, Thank you so much for nice explanation, I have a doubt at 02:00. How to apply dynamic programming for this problem? We are thinking of series of decisions on which vertex to choose next for optimal solution. Do we have a list of decisions to choose from? The only decision i see here is: choosing an edge with minimum weight. The same we follow in greedy method as well. Please clarify sir, when you find time. In dijkstra algo also, we choose which vertex to explore next.

[@shaikhmukhtar8072]

In greedy approach, we directly go another vertex which is min cost. But in this we go every vertex by stages in graph . Then we have to choose min of them.

[@nishitkakkad4976]

Sir, what if there is an edge between vertices in same stage like 2 to 3 in stage 2 or 7 to 8 in stage 3. Will this formula work in that scenario?

[@mearaftadewos8508]

NO. It's only for multi-satge meaning every vertex is connected to the next stage.

[@aadarshmishra1488]

sir i think here one lit bit mistake in cost(3,6) mean third stage 6th vertex but we write the equal cost(3,6)=min{cost(6,9)+cost (4,9)....and so on where cost(6,9) means 6th stage 9 th vertex which is wrong how can we write sir?

[@roshithborra4713]

great explanation sir

[@khenir99]

Meri dua hai ki app aur 100 saal jiyo abdul baari ji, mai chahata hu ki mere bacche ke bacche ko bhi aap algorithm sikhao

[@hann06_.]

Astonishing video sir, thankyou for providing a video on this topic.

[@ekosaputra5887]

Amazing explanation sir, it helps me to understand the concept of this topic 👍👍

[@johnc4624]

Thanks for the exhaustive explanation. Can you give account for the revelance of needing stages in the formula?

[@aguy9371]

simple yet very easy to grasp, thank you sir!

[@devashiskhandelwal598]

Sir if there is a path from i th stage to (i+2) th stage will it be still a multi stage graph and can we solve it by dynamic approach?

[@_rahul_jay_2813]

watched every vedio just one time and I'm going to write exam tmrw💝

[@merflyco4152]

Thank you for the clear explanation. It really helps.

[@sachitank9287]

Superbly Explained

[@kumarshivam8077]

Sir, we are applying the greedy method approach. For example, we are going to a local maxima everytime. So please clear this to me?

[@apoorvmishra704]

Sir, there is confusion when you are generating g(2,{3})=15 but later on g(2,{4})=8, but it should be 18 as g(2,{3})=15(same way)

[@pushpagaddi1682]

Sir this multiple stage graph may also possible in backward then we use the same formula...for solving in backward

[@giorgi23]

Big respect Sir. I have one question. What stages do in programming or they are used only for visual presentation? What they tell us? If we remove them what would happen?

[@adityaojha2701]

Because we visit vertices stage-wise to find the cost.

[@nikhilnagdev641]

Thanks for explaining it in the best way :)

[@sasikanth8378]

In search of gold we lost diamond love u sir 👍👍

[@joschk8331]

Thanks for giving away such an informative video for free!