Shortest Path Algorithms Explained (Dijkstra's & Bellman-Ford)
Вставка
- Опубліковано 6 чер 2024
- To further enhance your computer science knowledge, go to brilliant.org/b001 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
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.
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.
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 ?
: : gajah mada
#poxi
#coin
#boxi
#asia
#osis
#intel
#sony
#linux
sumarecone : :
europe_negara@keraton
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.
I was just thinking about this! Thank you
Loved your videos and animation! Mind sharing what software you used to make all these animations? (hope it's not just After Effects 😂)
Best video to watch 3 days before my data structure exam
Bro this is algorithm not data structure 😂
@@deependrakumar5239 My lecture covers graph search algorithms 🙂↔️
@@deependrakumar5239 It includes search algorithms related with various data structures bruh
I understand your feeling brother, but we use algorithm in data structure to make effective and scalable code.
@@deependrakumar5239 I get it. I just wanted to say that this video helped me understand the algorithm much better
Great content young man !
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?
he probably uses PowerPoint like CoreDumped
and I'm not joking when I say that
@@vastabyss6496 When I think about it, it's not a bad idea. Thanks 🙏🏼
Or, manim!?
@@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
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
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.
OMG he's alive!
Great explanation, very understandable.
A question: What software do you use for these animation, and illustration?
Was literally doing this chapter of Grokking Algorithms this morning.
How do you know or find a way to determine the weight for each edge?
I love theas vids so much i missed them ❤
Thank you 😊
Finally it's been a long time
thats why i fkin love cs
A few days before I have hard time to understand bellman ford algorithm. I like how you have explained two algorithms in just 13 minutes.
just bump all values by some amount such that the smallest negative becomes 0?
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
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
A* in python next please ❤
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.
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.
Salute 🙌
Bravo 👏👏 Lit 🌠 Impressive ❤ Gratitude 🥳✨ for your satisfactory Work 🚀🌟🌱
what about if some of these are highways
Then the weight of those edges will be less, assuming that the computer is using time and not distance as its cost function.
The algorithm doesn’t know the shape of the map, just the distance (in time) between intersections.
bravo
A* My beloved
What's the meaning of your UA-cam channel's name !
Originally, it was b001ean, using boolean values 0s and 1. It was later just shortened to b001 (pronounced “bool”)
Duh, the shortest path is obviously a direct line between the points /j
yet gives you the longest path
first
I'll take things that annoying to hear both on UA-cam and in bed for $100.
Finally you are back