Dijkstra's Algorithm vs Prim's Algorithm

Показать описание

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

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.

Рекомендации по теме

Комментарии

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

BackToBackSWE

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

ElfHimSelf

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 ;)

Ruby-mrgn

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

DJalyssagail

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

arrahul

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

davidbellamy

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

cphash

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!

sams

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.

thezanycosmophile

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

dab-city

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!

rishabkumar

Just found your channel. I never liked learning about algorithms, time complexities... because it was too confusing and very dry (talking about that CLRS

But the way you present content makes it very easy and interesting to learn about these topics now!

qbertrtrtg

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

thecsprof

Very precise and clearly presented! Thanks!

DarkDICE

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

neon_