Shortest Path Algorithms Explained (Dijkstra's & Bellman-Ford)

Рет қаралды 49,357

Күн бұрын

To further enhance your computer science knowledge, go to brilliant.org/... to start your 30-day free trial and get 20% off an annual premium subscription.
If you want to experiment with the algorithms yourself, I've included some Python scripts on my Patreon: / b001io
💬 Discord: / discord
🐦 Follow me on Twitter: / b001io
🔗 More links: linktr.ee/b001io

Пікірлер: 68

@landchannel7688 3 ай бұрын

10:25 Ok but the idea of an electric car just going in circles between charging stations, hogging up more and more charge is genuinely funny.

@priyanshumaity6780 3 ай бұрын

I know that you probably have answered this question quite a lot of times, but if you don't mind can you please tell me what software you use to create these animations?

@vastabyss6496 3 ай бұрын

he probably uses PowerPoint like CoreDumped

@vastabyss6496 3 ай бұрын

and I'm not joking when I say that

@priyanshumaity6780 3 ай бұрын

@@vastabyss6496 When I think about it, it's not a bad idea. Thanks 🙏🏼

@chry003 3 ай бұрын

Or, manim!?

@vastabyss6496 3 ай бұрын

@@chry003 Manim and Motion Canvas are great, but I don't think that's what's being used here. If there was an algorithm being visualized that was doing tens or hundreds of operations, then using something like Manim would be best since it would be a pain to animate that all by hand. For this video though, it seems like animating it by hand wouldn't be too hard

@janaafifi1410 Ай бұрын

you are a genius I hope you always have a cold side on ur pillow sir

@MoeSalamaIbrahim 3 ай бұрын

Throughout this year's courses in my master's degree in electrical engineering, I've encountered Dijkstra's algorithm in almost all of my courses. I've never ceased to keep searching for explanations and perspectives of it, given my non-CS background but the sheer number of applications to this algorithm. Also, this year has made your channel one of my most enjoyable sources of informative relief. Thank you sir.

@CraftingCake 3 ай бұрын

What specialty did you do in your masters? I have a bachelor in electrical engineering and we never talked about algorithms at all. I would even say, this is what differentiates me the most compared to computer science students.

@1.0 3 ай бұрын

Duh, the shortest path is obviously a direct line between the points /j

@realdlps Күн бұрын

My genius fix for those negative loops is just assuming they don't exist... Take the largest (or well technically smallest) negative weight in the graph, then subtract that from all weights in the graph. Now the smallest weight is 0, and the problem is kind of "solved" and you can find a path. This probably has a lot of problems, but it does get you a solution, which many times is better than only being able to say that "yeah, there's a loop that breaks my algorithm"

@TheGoldenPro 3 ай бұрын

OMG he's alive!

@PunamTish 3 ай бұрын

What's the meaning of your KZbin channel's name !

@b001 3 ай бұрын

Originally, it was b001ean, using boolean values 0s and 1. It was later just shortened to b001 (pronounced “bool”)

@marvinchuakhaichien2361 3 ай бұрын

Loved your videos and animation! Mind sharing what software you used to make all these animations? (hope it's not just After Effects 😂)

@Blaze_0101 3 ай бұрын

00:01 Finding the shortest, optimized path is crucial in daily life. 01:32 Dijkstra's algorithm is a key solution method for finding shortest paths. 03:01 Using Min Heap priority queue to find shortest paths efficiently 04:48 Dijkstra's algorithm finds the shortest path 06:36 Dijkstra's algorithm cannot handle negative weighted edges 08:22 Finding shortest paths using relaxation technique. 10:08 The Bellman Ford algorithm can identify negative weight cycles in a graph. 11:42 Negative weight cycle problem is an ongoing area of research. Crafted by AI ?

@adhitamaputra-73 3 ай бұрын

: : gajah mada #poxi #coin #boxi #asia #osis #intel #sony #linux sumarecone : : europe_negara@keraton

@DIGITALPEPacksyCursos 2 ай бұрын

7:46 Bellman-Ford

@abderus4220 Ай бұрын

Maybe I'm wrong but wouldn't that problem with negative numbers be solve if you prioritize nodes with no active predecessors instead of min values?

@vader567 3 ай бұрын

thats why i fkin love cs

@dlv5652 3 ай бұрын

I was just thinking about this! Thank you

@chri-k 3 ай бұрын

One thing: for Dijkstra's algorithm, if you're going to visit every node (so, if you have a small-ish graph), there's no reason to use a min heap

@robinsonrojaslopez5200 3 ай бұрын

I don't know much about how the algorithm works, but if you are looking for the smallest value, I understand that it cannot be less than zero since this way you would avoid the problem of entering a cycle in which the value is decreased. infinitely, to prevent the value from being less than zero you can look at what the weights are and look for the smallest one, in the first example -30, and add the absolute weight in the rest in this way this node (and the others with existing negative values) has a value equal to or greater than zero and the problem is avoided.

@Milenakos 3 ай бұрын

just bump all values by some amount such that the smallest negative becomes 0?

@asston712 3 ай бұрын

that doesnt work. Say we have a graph with each edge bumped up by N distance. If we have a certain path that passes through 3 edges, the total bumped distance will be 3*N longer than the actual distance. However, consider a path that passes 5 edges, this path will have a total bumped distance 5*N longer than the actual distance. Bumping unfairly favors paths that travel over fewer edges. A concrete example is lets say we have 2 paths we can take: 1,1,1,1,1,1,1 or 20, -10 we know the top path is more efficient, but after bumping each distance by 10: 11,11,11,11,11,11,11 or 30,0 the bottom path becomes for efficient

@Pogoda450 15 күн бұрын

Amazing video!!

@keithmorgan6498 2 ай бұрын

Perhaps too simplistic but if you have a path of -25 on one vertex add 26 to all paths so that every path is positive. Then you could use Dijkstra's algorithm. :)

@Leon-eu7od Ай бұрын

Excellent explanation! Can I ask which software do you use to create this fantastic animation video? Thanks a lot!

@DeokbaeKwak 3 ай бұрын

Best video to watch 3 days before my data structure exam

@deependrakumar5239 3 ай бұрын

Bro this is algorithm not data structure 😂

@DeokbaeKwak 3 ай бұрын

@@deependrakumar5239 My lecture covers graph search algorithms 🙂‍↔️

@DeokbaeKwak 3 ай бұрын

@@deependrakumar5239 It includes search algorithms related with various data structures bruh

@deependrakumar5239 3 ай бұрын

I understand your feeling brother, but we use algorithm in data structure to make effective and scalable code.

@DeokbaeKwak 3 ай бұрын

@@deependrakumar5239 I get it. I just wanted to say that this video helped me understand the algorithm much better

@Jaiden-2013 3 ай бұрын

Is this true: the most battery path is Bellman ford algorithm but set the starting location to “max battery” - “current battery” and disallow vertices to be negative

@jshet 3 ай бұрын

Was literally doing this chapter of Grokking Algorithms this morning.

@CultureofSpeech 3 ай бұрын

Salute 🙌 Bravo 👏👏 Lit 🌠 Impressive ❤ Gratitude 🥳✨ for your satisfactory Work 🚀🌟🌱

@jamescollier3 3 ай бұрын

what about if some of these are highways

@Loaderdani 3 ай бұрын

Then the weight of those edges will be less, assuming that the computer is using time and not distance as its cost function.

@Loaderdani 3 ай бұрын

The algorithm doesn’t know the shape of the map, just the distance (in time) between intersections.

@na50r24 3 ай бұрын

Question: Dijkstra should work for any graph as long there is no negative weight, no? Being a DAG is not a requirement for Dijkstra. Not sure if this is a weird question but Dijkstra is greedy but happens to work. Isn't there a non greedy Dynamic Programming approach to the shortest path problem? The reason for the second question: I think DAGs are graphs that can be actually solved with topological sorting and DP but I could be wrong.

@b001 3 ай бұрын

Correct, being a DAG is not a requirement for Dijkstra’s, nor is it a requirement for Bellman-Ford as long as the cycle isn’t negative and reachable by the source. I choose a DAG so that I could use the same graph throughout the video, so that once I created a negative weight edge, it ensured no negative weight cycle could exist so that the Bellman-Ford algorithm could solve it.