No video :(

Dijkstra's Algorithm vs Prim's Algorithm

Подписаться 240 тыс.

Просмотров 69 тыс.

50% 1

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe.com/coaching
This is a video walking through & contrasting Dijkstra's Algorithm & Prim's Algorithm based on the greedy choices each algorithm is optimized to make.
Prim's algorithm optimizes for the min-cost edge that connects the subset of vertices not in the minimum spanning tree to the subset of vertices in the minimum spanning tree we are trying to expand. We ensure every iteration we are choosing the min-cost edge that crosses the cut (wikipedia: a 'cut' is a partition of the vertices of a graph into two disjoint subsets).
Dijkstra's algorithm optimizes for the shortest cost path to get from the start vertex to a given vertex. We ensure every iteration we are improving our tentative costs from a fully optimized vertex.

Опубликовано:

3 окт 2019

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 104

@BackToBackSWE 4 года назад

Table of Contents: Introduction 0:00 - 0:41 Tracing Optimal Solutions 0:41 - 1:26 Dijkstra: Walkthrough 1:26 - 13:42 Dijkstra: Visual 13:42 - 14:36 Prim: Walkthrough 14:36 - 19:23 Prim: Visual 19:23 - 19:48 Reviewing What We Learned 19:48 - 20:35

@inversemetric 4 года назад

I heard that Dijkstra's algorithm does not always work well when the edges have negative weights. I considered if it would be possible to correct that by adding the absolute value of the most negative weight to every edge. It turns out that does not yield the correct answer unless you subtract that number * number of edges from the result for each path. This is probably common knowledge but seems fascinating to me.

@BackToBackSWE 4 года назад

@@inversemetric Yeah, I messed up in saying that, I went back to verify and dijkstra's only operates on graphs with positive edge weights, I made that comment on the spot with no diligence.

@ElfHimSelf 4 года назад

Got an offer from Lyft for the 2020 Software Engineering internship. Your videos helped me while studying 🙌

@imabeastyaok 4 года назад

Toss me some money bro...those lyft salaries are crazyyy 😂🙏

@BackToBackSWE 4 года назад

Where's my 10k at? jkjk, yeah, my friend just did Lyft. 💩's wild. Happy things went well.

@Naradmaxwell 4 года назад

man, how did you make it?? please tell, it will really help me in getting an internship.

@aj-kl7de 4 года назад

@Ruby-mr1gn 3 года назад

Dijkstra and Prim are used for dealing with different types of graphs and solving different kinds of problems: Dijkstra: Directed weighted(only allow non-negative weights) graph, find shortest lowest cost path from starting vertex to destination vertex; Prim: Undirected weighted graph, find lowest cost path to connect all vertices in this graph. Hope this helps ;)

@BackToBackSWE 3 года назад

yes

@priyamvashi2187 2 года назад

we can also apply Dijkstra to Undirected weighted

@DJalyssagail 4 года назад

i get excited when i search for an algorithms topic in youtube and your video appears. great explanation and teaching technique as always!

@BackToBackSWE 4 года назад

thx

@arrahul316 4 года назад

The effort that you put at a very granular level is something truly commendable. This is the first time I understood both of these Alg and probably one of the the best 9 am to 10.30 am on a Sunday

@BackToBackSWE 4 года назад

great

@pavithra977 4 года назад

Appreciate what you’re doing so much! You have the right attitude for video, and your sincere efforts are visible to make us understand better. Thanks again.

@BackToBackSWE 4 года назад

@davidbellamy1388 4 года назад

I'm new here and don't know when you started, but you are underrated.

@BackToBackSWE 4 года назад

hahahahahaha, welcome to the 💩 show, please be seated

@cphash 3 года назад

I specifically search for your videos whenever I want to understand the concepts. Thanks a lot for the content!

@BackToBackSWE 3 года назад

nice!

@sams7068 3 года назад

Great video, these are simple concepts but the way you tracked each node's parent in Dijkstra's Algorithm was a lifesaver. I was getting so bogged down in just maintaining my busy tree with arrows, etc. Saves a lot of confusion!

@BackToBackSWE 3 года назад

Glad you liked it

@Dark1DICE 7 месяцев назад

Very precise and clearly presented! Thanks!

@saravanprathi6956 4 года назад

Thanks a ton for this video, it really helped me!!

@BackToBackSWE 4 года назад

sure

@throwsand2 2 года назад

you videos are super helpful, thanks so much!

@dab-city 4 года назад

this video just saved my gpa for real thank you thank you sir

@BackToBackSWE 4 года назад

Sure.

@thecs490prof2 4 года назад

Dude I love your lectures! I use them constantly to help prepare my own lectures for my Advanced Algorithms class :)

@BackToBackSWE 4 года назад

nice - hey

@thecs490prof2 4 года назад

@@BackToBackSWE Btw if you're interested, I'd also be interested in a collab! I have a lot of students in my class, and I'd be happy if you wanted to do a guest lecture or make a small guest appearance :D It might be beneficial to you as well because some of my students might end up investing in your platform as well! Hit me up if you're interested - sr66+collab@njit.edu

@qbertrtrtg 4 года назад

Just found your channel. I never liked learning about algorithms, time complexities... because it was too confusing and very dry (talking about that CLRS book.....) But the way you present content makes it very easy and interesting to learn about these topics now!

@BackToBackSWE 4 года назад

Nice! glad to hear

@francescopiazza4882 7 месяцев назад

Very good, thanks !

@rishabkumar4940 4 года назад

My friend was asked this question in an interview, he was very confused as the two algorithms do totally different jobs so how can they be compared. But now I understand that they are very similar. Thanks!

@BackToBackSWE 4 года назад

sure

@NinoCuteCute 2 года назад

Nice,help me a lot

@ANGELINK999 4 года назад

Awesome video!

@BackToBackSWE 4 года назад

thx

@elleb6018 3 года назад

Thank you ❤️

@silviapetrova8562 2 года назад

Thank you

@ShaliniNegi24 4 года назад

This guy is a Gem!

@BackToBackSWE 4 года назад

no ur a gem

@jayjin 4 года назад

Could you please make a video to explain Leetcode #4: Median of two sorted arrays. Thank you in advance!

@BackToBackSWE 4 года назад

yeah

@judgebot7353 Год назад

thanks

@neon_342 Год назад

Hello @backTobackswe. I love your lectures. After 6 months of doing research, I came to a solution that I need to purchase your course only. And I did it also. Can you please bring a series of lectures of DSA concepts. Not only solving questions. But what is what and how to create from scratch and its internal working in Java

@BackToBackSWE Год назад

Hi, thank you for your suggestions. Yes absolutely. We already have some videos explaining core DSA Concepts, you can find them here and on our platform - backtobackswe.com/ 😄

@neon_342 Год назад

@BaclToBackSWE are you going to add more questions on your platform ? Or remove some questions and in place of that adding new ones ? Are you going to add some OS, Networking, DBMS questions also in your package ? And how frequent you update your course content on your platform ?

@SunnyGuptaTech 3 года назад

Which microphone do you use to record your videos, the voice is crystal clear.

@BackToBackSWE 3 года назад

RODE VideoMic, the red one

@soumadip_skyy_banerjee 4 года назад

Love ur vids as usual!

@BackToBackSWE 4 года назад

@eugenemolokov3427 4 года назад

Nice to see you back :)

@BackToBackSWE 4 года назад

hey

@goodwish1543 4 года назад

Good idea to classify them. Thanks for teaching.

@BackToBackSWE 4 года назад

sure

@atulmalakar 4 года назад

Hey Ben this video was definitely very informative and nice like your other videos. However I have a request, can you please make a tutorial on maximum subarray sum using Divide and Conquer as there are not very good tutorials or blogs on the internet. I totally understand if you have different plans for your upcoming videos but this is just another fan request. Please give your suggestions.

@BackToBackSWE 4 года назад

I think I have a video on that, max contiguous subarray sum

@atulmalakar 4 года назад

@@BackToBackSWE yes yes there is, but it is Kadane's algorithm and what I am asking for is Divide and Conquer solution. Thanks anyways !

@BackToBackSWE 4 года назад

@@atulmalakar ah, true, I may

@adriandeveraaa 4 года назад

I have yet to take an algos course. Transition from EE to CS. What is a "greedy" algorithm? And what video should I begin in your series D:?

@BackToBackSWE 4 года назад

brilliant.org/wiki/greedy-algorithm/ and not sure?

@join2nitin 3 года назад

Can you please provide C# code implementation for problem "Find Shortest Path in undirected weighted graph from source vertex to each vertex", I have purchased your course but could not find code on your website.

@BackToBackSWE 3 года назад

Hey! We would love to, but right now we are rewriting everything from scratch and don't have too many resources to redirect (it is just 2 devs, us, right now). The new experience will be out in the middle of 2021.

@galbalandroid 2 года назад

For the MST, why didn't we favor A->B->G? that would yield a cheaper overall tree than going through A->F->D->G?

@inigo1880 3 года назад

MY DUDE IS RIPPED!

@parthokr 3 года назад

Can you make a video on bellman ford algorithm?

@BackToBackSWE 3 года назад

probably not it is niche and complicated

@TitanTubs Год назад

quality

@MiketheCoder 4 года назад

Now the bigger question is in what scenario would you use one over the other?

@BackToBackSWE 4 года назад

wym

@99ansh 4 года назад

Did anyone notice a bull shadow on the t-shirt? It's cool.

@BackToBackSWE 4 года назад

what lol

@TheKseth 4 года назад

@@BackToBackSWE My man is a Dwayne Johnson fan

@Naradmaxwell 4 года назад

how do you find the LOWEST COST VERTEX ??

@BackToBackSWE 4 года назад

not sure

@ilya1131 3 года назад

didnt understood the culc of D, how is AD longer then AFD if the distance between AD is 7, and the distance between AFD is 5+7=12 (in the video its somehow 6)

@eashanmathur560 4 года назад

In Prim's algorithm, why aren't nodes E and G connected? When you get to E, your only choice is to go to G so why wasn't that choice made?

@BackToBackSWE 4 года назад

I don't remember this video and dont have time to rewatch cuz replying fast

@eashanmathur2030 4 года назад

16:55

@annatvsf 3 года назад

@@BackToBackSWE I also was wondering why we ignored EG edge and same situation with CF edge later. Is vertex supposed to have more than one edge to choose the min from?

@supamdeepbains5172 4 года назад

Dear Mr.Back to Back SWE, Hi there, I hope you're doing well, I just want to say that wonderful explanation as always on every video, but which one would you prefer to be used over another bro? Thanks Warm Regards,

@BackToBackSWE 4 года назад

Hi, preference for algorithms? not sure what you mean

@supamdeepbains5172 4 года назад

@@BackToBackSWE Hi there , Yes bro for example which one is faster in order to use? Thanks Warm Regards,

@prashanthvaidya 4 года назад

Great video. :) Especially Prim's algorithm and the "vision" bit was spot on. One caveat though! You mentioned going back could help if there was a negative edge, but Dijkstra's Algorithm fails to find a shortest path for a graph with negative weights. Once a vertex is taken out of the heap, it is assumed that the shortest possible path for that vertex has already been found.

@BackToBackSWE 4 года назад

Oh true, good point, I remember saying that and questioning if it was true

@shantanutripathi 4 года назад

Why no one is talking about what if cycle comes in while selecting the minimum edge and then we have to check for condition of cycle?

@BackToBackSWE 4 года назад

i like your profile pic

@shantanutripathi 4 года назад

@@BackToBackSWE Tell the answer of the question or else I will come to you with 3 other friends of mine :)

@mohnishsinghbhamra 3 года назад

you explained Prims MST in a kind of kruskal way

@ShubhamKumar-rt8nb 4 года назад

why do you not choose the edge from F to G it also has a weight of 6

@ShubhamKumar-rt8nb 4 года назад

@@iklilios thanks to clear it

@BackToBackSWE 4 года назад

nice

@JavaAidTutorials 4 года назад

WAR between Dijkstra and Prims...:)

@BackToBackSWE 4 года назад

yes

@taehyeonkim3900 3 года назад

where is your emphasizing voice!?

@BackToBackSWE 3 года назад

wut

@jacekwzgorzeeliminujaczosl4036 3 года назад

What happens when we stop developing people and reach our goals? We can all decide. But we can fight with disease and easily destroy it. We have the right to punish others, including children. How safe are all the medical centers in Spain? During the shortest period of human history, the Spanish Empire conquered Porto del Sur. "I only do nothing but shoes. I want to improve your life in Scotland and Spain. The king has been his friend for centuries, you can only serve the poor and the average. Often in the military. People say that chocolate and tobacco production Are successful. ".