4.7 [New] Traveling Salesman Problem - Dynamic Programming using Formula

[@Nex_Addo]

You are going to single-handedly get me through my algorithms course. It's so clear, almost obvious, when you explain these things, where seemed so murky when I first heard them. Very much appreciated.

[@SadisticShade]

For my own reference: final path : {1,2,4,3,1}

[@rohitkandula8493]

You are a divine god for me ,tomorrow i have exam learning today from ur channel😊✨🔥

[@vishaladithya9703]

thank you sir for your easy explanation. the topics which i felt hard in class, you explained it so understandable.

[@mohammedadel8948]

Thank you for your hard work.

[@kinglygaurav]

@Abdul Bari What will be the time complexity of TSP when done this way? I am guessing Tabulation will reduce some amount of time but ultimately we are having to consider all possible routes from all possible vertices. Thus O(n!) correct?

[@hughjanus5342]

We love you sir!!!!

[@absiddiq2623]

Awesome 👍🏻👏🏻

[@jyotsnapriyadarshi8016]

Sir please provide the code also for some of the algorithms of which code has not been provided .

[@pranav288]

be grateful

[@mkhussain3099]

Cannot see overlapping sub problem

[@youtubecr3115]

Exactly what I was wondering

[@nayba100]

Where i can find the first formul that you used. Can you name your source please?

[@pearlminestudios7568]

Sir, why don’t you swap this video into the playlist instead of the old one.

[@Shivam-vr6eh]

Abdul Bari Sir my question is Can we use that old video method for Salesman Problem using dynamic prog?

[@ayasswain]

The best algorithm explaining teacher I have ever seen. Thanks Abdul Bari sir.

[@niranjanreddy6334]

Abdul Bari sir I randomly landed in your page , after that I cant stop myself from binge watching all your Algo videos , your videos are amazing n Iam loving it

[@unseenscenes3296]

Algo ki sb videos dekh kr ke bol skte ke yr mera kafi had tk algorithm clear ho gya Mtlb fir me ja kr k codeforces wagera ki c type problems solve kr pao ga

[@arpitaarpi7015]

Dear sir, This semester is very short, 3 months approximately So our professor can't complete the whole syllabus But our college professor is referring your channel for learning You are awesome sir❤

[@AnitShrestha]

Thank you. I found deriving the formula, than implementing one more effective. But it was nice to see the other way as well.

[@souravkumarskb7131]

11:36 apke sath ek chota sa prank hua, camera ke saamne dekh ke smile karde

[@sudhagbhat8226]

U r out of mind

[@divyanshutripathy3484]

@@sudhagbhat8226 He was just joking, don't take it seriously.

[@s.a.h.q9389]

😂🔥

[@asheeshmathur]

Good, is this part of some of your Udemy course. Please advise.

[@theperennialbaker5264]

Awesome explanation Sir... 👍👌 Thanks alot... 💕

[@pralaykumarlahiri3788]

If in the source matrix, position [3,1] value we change it as value '0'. Then what should be the Path?

[@Deepak-jk1eh]

this video is much clear than previous one give a medal to this man

[@vishalc832]

00:01 Explaining the traveling salesman problem using dynamic programming formula. 02:15 The formula explains how to find the minimum cost for visiting the remaining vertices. 04:12 Finding the minimum value by using dynamic programming formula 06:06 Dynamic programming for solving traveling salesman problem 08:27 Discussing the recursive tree execution for solving the traveling salesman problem using dynamic programming. 10:27 Dynamic programming is done with tabular values. 12:43 Finding smallest values first using dynamic programming 14:47 The shortest route for the Traveling Salesman Problem using Dynamic Programming is 35.

[@vakhariyajay2224]

Thank you very much. You are a genius. 👍👍🔝🔝🙏🙏👌👌

[@mohammedkhan7029]

kya yaaro chale jaate aisich class se sikhaana chodhke unsubscribe dislike

[@Wizzy404]

you the GOAT at this.

[@VijayKumar-tt6tj]

Sir, I'm a great fan of your videos, You make things really easy for us no matter how complex the problem statement is. Since the time complexity of this algorithm is not polynomial, AFAIK we can just find the MST (Minimum Spanning Tree) and can add the Cost from last vertex to the source to the final result. This way we can have only O(E log V) complexity? Please correct me if i'm wrong?

[@aronquemarr7434]

You cannot revisit a city in the standard travelling salesman problem.

[@devashreerane4867]

Hello Sir, Which reference or standard book is preferred for referring algorithms ?

[@anmol4893]

Introduction to algorithm by comren

[@aparnasai9641]

Very nice explanation sir super super

[@vipinkumartripathi5022]

what's the use of making table.....I mean what optimization we are achieving by using dp

[@diegochicurel4724]

It would have been nice if he showed the table at the end. But basically, you start from the bottom and fill the values in the table, then you don’t need to do recursion or anything else, just fill the table and check if the values are already defined (they will if we do it this way)

[@sarfarazbaig1898]

I got more benefits by learning from this video,it is very nice video👌.

[@shaikobaid3528]

Really satisfying 👌

[@wirito]

Professor, I asked you this in a different video but I have noticed the following: If I click on your course for data structure, it sends me to Udemy with a price of $10 which is correct but it clearly says that this offer is for “new students only”. Since I already have an account, as soon as I log in the price goes up. I could create a new account with a different email but I am hoping you can look into this. I have also noticed that at random times on different days, the offer is different. Sometimes is $170, other times is $90, or $19 etc. I don’t believe the offer will be $10 during thanksgiving promotion as you stated. But even if it is, please let me know if the only option for me is to create a new account so that I can pay the $10. I am a college student and while I could pay $20 (which is what it goes up to when I log in if the offer is $10) I am suffering from greedy syndrome. You see, since you have already advertised it as $10 then I only want to pay $10 :). That’s how greedy algorithm works professor! I can’t go on paying $20 when there clearly is a lower weight Lol Please let me know!

[@starattaker4803]

At -5:41 jo pachak hua , sir kehte ye method to lamba hai ye nahi karna 😭 yaar ek din pehle padhrai aur ye dekhne ko mile , LOL ho gaya 😂

[@josephsylvan6511]

what's the time complexity of this algorithm?

[@basujayanta1]

If there are more vertices present, say 6, then this algorithm becomes almost too huge to handle and cumbersome!!!

[@tanushreeagarwal4151]

it is appearing so but see from computer's perspective ..when we gonna program then its just A matter of a loop for controlling value of k.

[@reddy6131]

But u didn't say the shortest route

[@vishalc832]

Plot twist at 11:41

[@aarzooshaikh2688]

very good explanation sir.....guys watch him if u want to learn

[@shivanshusuryakar8692]

we are already :)

[@shanerelish3762]

thank you so much for this video.. i was a little confused with the formula.. now i feel dumb for not understanding it before.. 😅

[@fauguswanto6595]

Amazing content! Thank you !

[@ashishg656]

Very good explanation, watched lot of videos :) Thanks a lot for such awesome content.

[@valerian2768]

Incredible Explanation!!

[@srinivb1]

As usual AWESOME explanation by Abdul Bari sir. Kudos to you for explaining complex topics in easy and simple terms.

[@GautamNishant]

Thanks a lot SIR! very helpful :)

[@dishasuresh4813]

Can somebody give me the previous video on traveling salesman problem he is referring to please?

[@pujithagaddale7171]

Sir can we do exactly in exam like drawing tree and writing remaining vertices???

[@amanmanna8976]

Depends what type of pattern your university follows .....

[@SRNR_PODCAST.]

a goldmine in youtube

[@anandbaskaran]

In an iterative approach, you can simply solve it as you show in the tree diagram.

[@abdullahmeo]

What about the return path - imagine u have the case where the return path for a vertex is shorter if we use an indirect route. Would you just run the algorithm backwards?

[@ramaarahatekar1570]

so how and what are we supposed to write it in college university end exam? I mean, where do we start? Do we draw the tree with sample calculations or do we directly do calculations by formula?

[@sohamghosh533]

Do everything 😂😂

[@rohitkandula8493]

The Man The Myth🫶🔥

[@aditiranjan303]

What is the vedio no. For previous vedio on this topic as said by sir?

[@basobpaulbrinta3198]

how are we gonna use tabulation method for this one?

[@bhargavakhani4921]

Sir can you please solve for s1=abbacdcba and s2=bcdbbcaac

[@saksheegoel2654]

Where is previous video sir? Tmw is my exam can you give the link ?

[@talharashid7703]

Paatal Lok,s Jaideep Ahlawat.👍

[@parulgupta179]

Finally got it thanx

[@anjaneyaagrawal1882]

algo bhi bata dete toh thek rahta..................hehehe

[@vidyamkaushik8796]

How to find the path?

[@fatimamaj7964]

Thanks for the tutorial. I would like to just add one note. Maybe it is better to go through tree as Depth-first search not Breadth-first search, because I think recursive algorithm use Depth-first Search.

[@vaishnavikotapati3196]

Superb explanation Sir hatsoff🙏🙌🙌

[@anjalian6314]

Sir can you explain cutting plane algorithm

[@nikhilkumarjamwal5322]

Long but easy question with awesome explanation!💫

[@inevitablegaming9365]

Saviour ❤️

[@RohitKumar-xn8ez]

Sir, why C[2][1] and C[1][2] have different values and similarly for others.

[@justwanttoknow4621]

1st city se 2nd city jane pe Ola mili bro Aur 2nd se 1st jane pe uber Ab bhai jo mehnga h wo mehnga hai🙅‍♂🤷‍♂😛 Just kidding Actually they are predefined weights of path available for the salesperson. Suppose it like a two different root from going 1 location to another location. Assume each vertex as a city/country in the world and there are multiple paths for every city from another city. The available data is just the indication of the salesmen didn't choose the same path. Agra->Delhi Delhi->Agra There are multiple roads available for this Assume A(agra)(delhi) = 12 and A(delhi)(agra) = 13 Then the path for reaching delhi and returning back from there might be different. It's just given. Hope you got it.

[@mona5711]

legendary thanks a lot!!

[@atharva808]

thank you sir thank you so much 🙏🙏🙏

[@AnkitSoni-vm5od]

Your algorithm lectures is really awesome....!!

[@paulsnehasish5830]

how do you do the table without writing the recursion tree first? we have to write the recursion tree in order to know the later values

[@Mansoor-qf3mw]

Watch few of his prev. videos on DP u will get it. In a table u don't find 'later' ones but 'previous' ones or from where the subprob came. Actually if u find the value of the smallest subproblem then u would be able to find the answer to thelarger subprob and so on.. Inshort u start from small and then form large.

[@pavan7432--]

11:37

[@aroo1377]

Sir you are awesome.. Thank you

[@nikitasinha8181]

Thank you so much sir 👍👍👍🙏🙏🙏

[@anjaneyaagrawal1882]

thank you very helpful

[@ريماآلنزال]

Please, I want an algorithm for this problem. I want to transfer it to program c # :( if you allow

[@ريماآلنزال]

Please help 🥺🥺

[@SandeshMotoVlogs]

U will get it on gfg

[@devanshmesson2777]

Is it a bottom up approach?

[@bhuppidhamii]

Thankyou sir

[@SindyanCartoonJordanian]

Thank you very much , May Allah bless you

[@saisravani2625]

Sir how do we do the table without writing the recursion tree first? we have to write the recursion tree in order to know the later values

[@manishrai6845]

simple find 2 to null three to null four to null then get the values similarly 2 to 3 2 to 4 then 3 to 2 and 3 to 4 etc . Or use the formula which he's given in the beggining of this video (g[i,s] one ).

[@chaoluncai4300]

@@manishrai6845 i think if using formula we have to do like a top down memoization dp, i can't think of a effective way for bottom-up dp yet, like how do we know the remaining set if starting from the bottom (from 2-> null etc.)?

[@shahinpathan5705]

It will be found in hindi

[@saadbinkhalid4208]

Thank you so much Sir. You make it really easy to grasp and apply these concepts. I am even doing your course on Udemy. Hope to see more of your content and your channel grow even vast. Best Wishes.

[@nigadenagendrasunil8503]

One Doubt! The formula you explained is for minimum spanning tree. I think you should explain the last condition when a set is empty we have to return distance from the last node to the starting node. Anyways, Its been great to watch your videos. Kudos to you!

[@jDelicious___]

He did explain that

[@pratikkumar6148]

best playlist in algorithm cheers

[@unseenscenes3296]

Bhaiyaa ye series complete kr ne se algorithm ka kaafi part cover ho jye ga

[@sonalgoje]

You are awesome sir , it's very nice and clear explanation. 👏👏👏

[@thefuntech2810]

Can we apply a dijikistra algo to find the path ...

[@AdeshPaul]

No, because you've to traverse back to the source vertex.

[@mfaraday4044]

thank you sir

[@tushardalave4619]

Thank you sir

[@kharouddavindersingh2237]

great explanation.

[@abirpaul9027]

Best teacher for Algorithms

[@abhishekjha1658]

excellent explanation sir..... please explain the implementation of algorithm too...!

[@ashishsinha8893]

sir LCS problems I think u forget??

[@rvranjan99]

Great content and easy to understand.

[@LocNguyen-mn4dd]

thanks

[@allenhung4390]

awesome explanation!!!

[@nurel882]

Thank you

[@yashaswinisyashu3861]

🙏🙏🙏

[@ankitgunjal1116]

11:07

[@peasant12345]

n 2^n?

[@dimajangveladze3712]

Nice

[@AdeshPaul]

Thanks.

[@shriharrsha3541]

.

[@knoName5691]

superb :-) Thanks a lot sir :-)