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 ?
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.
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?
@@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
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.
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"
There's someone else who asked about that in the comment already, and here's the problem with it (quoted from @asston712): 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
Wait, this could work. You are just shifting the baseline of the cost of each edge upwards. At the end you still attain a result, if we want to find the actual cost, could we not just add the original value of the smallest value from the total cost of the path? What are the potential issues?
There's a problem with this, explained by @ashton712 in the comments (credit to them!): 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
Why in Dijkstra's method we hoard those pending vertex in a min-heap priority queue? Why can't we just using a normal queue to hoard those pending vertex like a bfs process?
In a queue you're prioritizing those who got added there first. But there's no inherent value with doing so in a weighted graph. What actually matters is the total distance up until that node. This translates directly to the fact that, in Dijkstra's algorithm, once you pop a vertex off the priority queue, you've found the minimum distance. Because in a graph with non-negative edges the function total distance vs time run is monotonically increasing, so once you pop off some distance x, all the remaining distances are at least x, which means that's the shortest possible distance from some vertex. Therefore, you can mark it as visited and not go through it again
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
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. :)
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.
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.
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
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
7:46 Bellman-Ford
I was just thinking about this! Thank you
Fantastic video, great explanation and visuals.
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.
Yeah but now whatever value you find has no meaningful interpretation
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
Was literally doing this chapter of Grokking Algorithms this morning.
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
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.
Loved your videos and animation! Mind sharing what software you used to make all these animations? (hope it's not just After Effects 😂)
OMG he's alive!
Excellent explanation! Can I ask which software do you use to create this fantastic animation video? Thanks a lot!
Very good video!
Great content young man !
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?
Finally you are back
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.
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"
There's someone else who asked about that in the comment already, and here's the problem with it (quoted from @asston712):
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
Wait, this could work. You are just shifting the baseline of the cost of each edge upwards. At the end you still attain a result, if we want to find the actual cost, could we not just add the original value of the smallest value from the total cost of the path? What are the potential issues?
There's a problem with this, explained by @ashton712 in the comments (credit to them!):
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
@@RobinLogic paths with more nodes will get more additional costs
Yea this doesnt work
Amazing video!!
Why in Dijkstra's method we hoard those pending vertex in a min-heap priority queue? Why can't we just using a normal queue to hoard those pending vertex like a bfs process?
In a queue you're prioritizing those who got added there first. But there's no inherent value with doing so in a weighted graph. What actually matters is the total distance up until that node. This translates directly to the fact that, in Dijkstra's algorithm, once you pop a vertex off the priority queue, you've found the minimum distance. Because in a graph with non-negative edges the function total distance vs time run is monotonically increasing, so once you pop off some distance x, all the remaining distances are at least x, which means that's the shortest possible distance from some vertex. Therefore, you can mark it as visited and not go through it again
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
Great explanation, very understandable.
A question: What software do you use for these animation, and illustration?
+1
How do you know or find a way to determine the weight for each edge?
could be the lenght of a road, or as in this video the charge quantity. What I'm saying is that the edges weight have to be part of the previous data
I love theas vids so much i missed them ❤
Finally it's been a long time
you are a genius I hope you always have a cold side on ur pillow sir
thats why i fkin love cs
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. :)
Thank you
Thank you 😊
Salute 🙌
Bravo 👏👏 Lit 🌠 Impressive ❤ Gratitude 🥳✨ for your satisfactory Work 🚀🌟🌱
A* in python next please ❤
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.
Duh, the shortest path is obviously a direct line between the points /j
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”)
bravo
yet gives you the longest path
first
I'll take things that annoying to hear both on UA-cam and in bed for $100.