Dijkstra's Algorithm vs Prim's Algorithm

[@BackToBackSWE]

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]

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]

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

[@Ruby-mr1gn]

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]

yes

[@priyamvashi2187]

we can also apply Dijkstra to Undirected weighted

[@ElfHimSelf]

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

[@imabeastyaok]

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

[@BackToBackSWE]

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

[@Naradmaxwell]

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

[@aj-tg]

gg

[@arrahul316]

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]

great

[@DJalyssagail]

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

[@BackToBackSWE]

thx

[@davidbellamy1388]

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

[@BackToBackSWE]

hahahahahaha, welcome to the 💩 show, please be seated

[@cphash]

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

[@BackToBackSWE]

nice!

[@sams7068]

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]

Glad you liked it

[@thezanycosmophile]

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]

ye

[@rishabkumar4940]

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]

sure

[@dab-city]

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

[@BackToBackSWE]

Sure.

[@qbertrtrtg]

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]

Nice! glad to hear

[@galbalandroid]

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?

[@Dark1DICE]

Very precise and clearly presented! Thanks!

[@thecs490prof2]

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

[@BackToBackSWE]

nice - hey

[@thecs490prof2]

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

[@jayjin]

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

[@BackToBackSWE]

yeah

[@adriandeveraaa]

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]

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

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

[@eashanmathur560]

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]

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

[@eashanmathur2030]

16:55

[@annatvsf]

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

[@MiketheCoder]

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

[@BackToBackSWE]

wym

[@join2nitin]

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]

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.

[@SunnyGuptaTech]

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

[@BackToBackSWE]

RODE VideoMic, the red one

[@saravanprathi6956]

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

[@BackToBackSWE]

sure

[@throwsand2]

you videos are super helpful, thanks so much!

[@ilya1131]

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)

[@shantanutripathi]

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]

i like your profile pic

[@shantanutripathi]

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

[@goodwish1543]

Good idea to classify them. Thanks for teaching.

[@BackToBackSWE]

sure

[@atulmalakar]

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]

ok

[@BackToBackSWE]

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

[@atulmalakar]

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

@@atulmalakar ah, true, I may

[@99ansh]

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

[@BackToBackSWE]

what lol

[@TheKseth]

@@BackToBackSWE My man is a Dwayne Johnson fan

[@parthokr]

Can you make a video on bellman ford algorithm?

[@BackToBackSWE]

probably not it is niche and complicated

[@jacekwzgorzeeliminujaczosl4036]

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

[@eugenemolokov3427]

Nice to see you back :)

[@BackToBackSWE]

hey

[@ShaliniNegi24]

This guy is a Gem!

[@BackToBackSWE]

no ur a gem

[@mohnishsinghbhamra]

you explained Prims MST in a kind of kruskal way

[@supamdeepbains5172]

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]

Hi, preference for algorithms? not sure what you mean

[@supamdeepbains5172]

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

[@francescopiazza4882]

Very good, thanks !

[@inigo1880]

MY DUDE IS RIPPED!

[@Naradmaxwell]

how do you find the LOWEST COST VERTEX ??

[@BackToBackSWE]

not sure

[@NinoCuteCute]

Nice,help me a lot

[@ANGELINK999]

Awesome video!

[@BackToBackSWE]

thx

[@ShubhamKumar-rt8nb]

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

[@ShubhamKumar-rt8nb]

@@iklilios thanks to clear it

[@BackToBackSWE]

nice

[@soumadip_banerjee]

Love ur vids as usual!

[@BackToBackSWE]

yo

[@silviapetrova8562]

Thank you

[@elleb6018]

Thank you ❤️

[@taehyeonkim3900]

where is your emphasizing voice!?

[@BackToBackSWE]

wut

[@JavaAidTutorials]

WAR between Dijkstra and Prims...:)

[@BackToBackSWE]

yes

[@judgebot7353]

thanks

[@prashanthvaidya]

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]

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

[@TitanTubs]

quality