Dijkstra's Shortest Path Algorithm | Graph Theory
Вставка
- Опубліковано 13 чер 2024
- Explanation of Dijkstra's shortest path algorithm
Dijkstra source code on Algorithms repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/Algor...
Indexed Priority Queue Video:
• Indexed Priority Queue...
0:00 Intro
0:28 What is Dijkstra's algorithm?
1:13 Algorithm prerequisites
1:55 Video outline
2:28 Dijkstra's algorithm overview
3:50 Lazy Dijkstra's animation
8:10 Lazy Dijkstra's code
11:33 Ignoring stale node optimization
12:11 Finding the shortest path
14:01 Stopping early optimization
15:11 Eager Dijkstra's with an indexed priority queue
16:27 Eager Dijkstra's animation
19:28 Eager Dijkstra's code
20:31 D-ary heap optimization
23:06 The current state of the art for heaps
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
I agree with most people here. This is easily one of the best Dijkstra's Shortest Path Algorithm videos on the internet, if not the best one. I'm so glad that I found you. Thank you making this! ♥
Thank you for taking the time to make these videos.. They are tremendously useful. Hoping to see more in the future ....
Glad to hear you enjoy it!
This channel is very much UNDERRATED!!
Your videos were a HUGE help when I was doing a university course on data structures more than a year ago, and now I'm doing Advent of Code as part of my on-the-job-training. The subreddit kept mentioning "Dijkstra's algorithm" as a way to solve one puzzle.
I'd of course heard about it, but hadn't implemented it by myself before. But I immediately though "FISET will surely have covered it as well as he has his other topics..." And sure enough, this video helped me understand both theory and practice.
Thank you!
Thank you so much, I implemented it to Unreal Engine 4, for my RTS game. I used 100% of my brain for 3 days to make my own path finder, it worked but it was totaly slow
so how did you improve it later? : )
@@80kg I improved it by using this algorythm from video , instead of my own
@@lukay6230 Try A* and nice job :D .
😉
Thanks a lot! I love your videos, probably the most professionally done on UA-cam!
Most comprehensive video on Dijkstra. Thank you!
Outstanding series of videos.ur graph playlist is best on net.Thanks for providing these precious resources for free😃😃😍😍.
Hope u ll make series on advanced data structures like fibonacci heaps(for improving djisktra),binomial heap,suffix tree
Once again thanks for ur effort.
For anyone trying to implement this, you can solve leetcode 743 network-delay-time using this.
The whole BFS and Dijkstra thing clicked for me. Thank you very much!
Thanks
1:50 constraint is that graph can’t have negative weight edges
It is a greedy algorithm
Maintain an array/map mapping each node to the min distance we found for it so far. Initialized to inf
5:30 edge relaxation, a node is marked visited when we relaxed all its edges and update our best distances found
5:50 how priority queue works (with djikstra we use a priority queue for the nodes to visit vs a regular queue in bfs)
12:50 To actually reconstruct the path, keep another array/map of the previous node for each node when you update the shortest path found for it (the updated shortest path is the node we’re going to take)
Then you will have a map of Node to Node that maps a node to the previous node in the shortest path
13:00 logic for reconstructing the path from the previous array/map that associated a previous node with each of the nodes
Stopped at 13:30
Thank you for making the video! Much respect!
Amazing man. I thought the MIT videos were good, but YOU ARE THE MAN. You're content has helped me greatly for programming interview concept studying. KEEP IT UP and MUCH LOVE.
Great work very easy to understand
Came back here for a little refresher. Great videos!
I sometimes watch these too when I need a refresher 😂
Best ever found on the internet!
Not meaning to brag, but: I've stumbled upon an interesting recreational problem, entailing running 700+ dijkstra's algorithms on a graph of over 1mil nodes (whose adjacency matrix occupies 145GB of disk space). This video was of tremendous value to me, and thank you!
Really good, very practical!!!
Thank you for the video!
I wish to ask that the graph you chose at 16:30 to run Dijkstra on has a cycle, doesn't it? between the nodes 1 and 2
Hi, William! Thanks again for the great video. Just wanted to let you know that the link in the description that you said that redirects to the Indexed priority queue video actually redirects to your video on strongly connected components.
Thanks! Fixed.
You are an excellent teacher
Thank you so much for this one!
This is great. Thank you.
Wonderful, thank you! :-)
First of all, kudos for such an amazing content!
I was wondering for the optimisation step at 15:08 can we simply check if the index is visited and continue? (marking visited can be done after this step).
Is there any corner case we will miss in this?
In the optimization when there is an end node given at 15:08 , we could have checked if index == e before visiting the edges from the end node, as it is unnecessary as we already got the shortest distance to the end node. Please verify my observation.
Correct, I was going to point out the same thing.
you are perfect man...thanks
Impressive slides! Do you have a code to generate these slides? Or just type them?
In case someone like me is wondering why visited is used in the lazy implementation, the video states at 01:38 that once a node has been visited, its optimal distance cannot be improved. So having a visited set prevents going back to a previously processed node
This is because of the priority queue implementation, if u were using, simply queue u would have to check again and again, to ensure that the dist[node] has the minimum value. One could run even without the visited array part, but then it would simply be BFS without any benefits.
This is also in sync with the early stopping strategy, later described in the vid. This means that u will only visit a particular node when u have found the minimum distance of that node from the starting node. Quite cool, I would say.
@@sameerpurwar4836 I don't think we actually need a visited array.
This is because if an element is visited then we have already found it's shortest path.
So instead of maintaining a visited array can just check whether the new distance is less than the one we already have in the dist array.
This is something we are already doing, so I think even without the visited array we won't insert the node if it's shortest path has already been found.
Is my understanding correct??
@@rahulas721 yup, to be honest its cool, and it only becomes clear in hindsight.
@@sameerpurwar4836 Thanks a lot!
i love u. This us so effin useful
Hiii amazing video, about decrease key, can I use a hashmap + BST so that i can use the hashmap(maps node of BST by index) to delete and then insert the new edge.to and distance into the BST ?
That would be much easier to code in an interview compared to IPQ
Maybe no need of the BST also, just a multiset() and hashmap to multiset iterators?
Amazing content! Instead of using a visited array, is it enough we check for the condition dist[index]
yeah that's what I was wondering too. I tried it out and it doesnt seem to add anything and logically it seems redundant
15:00 Is it possible to break from the loop as soon as we encounter our destination/target vertex without having to process all its neighbors?
Huge help ✌🏻😍
very helpful!
I am confused about this: when we relax a node v, this means that node v CANNOT have been visited (since we found a smaller distance to it meaning it is not yet popped from the heap which means it is not yet visited). So this means inside the if statement where we relax a node, that node's visited should be false. I tested this in codeforces but it failed
This also brings me to a similar question. why do you have if vis[edge.to]: continue ? the if statement for relaxing a node can only be entered if vis[edge.to] is false so there is no need right? but this fails for some reason in codeforces
Best explanation out there of Dijkstra's. Period.
12:10, heap will ensure the tuple with the shortest distance of an index is picked first and then explored. When we come to the stale entry, can't we simply use the visited set to discard it instead of the highlighted check?
@WilliamFiset
19:30 it seems like you no longer need the line
if dist[index] < minValue: continue
because the ipq.decreaseKey will make sure you never have the same index polled twice. Is that correct?
Also, I have this question. I do not see the "greedy" part in this implementation. I am wondering whether this implementation will actually work correctly with negative length edges because we actually revisit the already computed lengths and update them, so if we discover a negative length edge, we might update the length correctly. Or am I missing something?
Yes, I think it should be ok to remove dist[index] < minValue with the ipq since there are no more stale nodes. I would still say that the algorithm is greedy since the next best node is still getting polled for the priority queue.
@@WilliamFiset-videos Thank you for your great work! Earlier today, I checked, I added stepCount variable and computed the shortest path with and without that check. The number of steps is the same. Moreover, I was surprised to see that the number of steps equals the number of edges for my dense graph. I have 200 nodes, and 3734 edges, and I do the check exactly 3734 times. I expected that number to be n logm, but it's only m. Are we down to O(m) running time? My current main loop looks like this:
while(!pq.isEmpty()) {
nodeId = pq.pollMinKeyIndex();
visited[nodeId] = true;
curNode = allNodes.get(nodeId);
//int curDist = pq.pollMinValue();
//if(dist[nodeId] < curDist) continue;
for(List child : curNode) {
stepsNum++;
int childId = child.get(0);
if(visited[childId]) continue;
int childDist = child.get(1);
int newDist = dist[nodeId] + childDist;
if(dist[childId] > newDist) {
dist[childId] = newDist;
}
if(pq.contains(childId)) {
pq.decrease(childId, dist[childId]);
} else
pq.insert(childId, dist[childId]);
}
}
The test data is Tim Roughgarden's file for his Algo course part 1: dijkstraData.txt
@@MykolaDolgalov I think that's expected since there are only m edges in the graph. The additional log(n) work comes from the insert and decease operations associated with the PQ, so the time complexity is still on the order of something like ~m*log(n).
Never heard IPQ! Thanks
thanks a lot man
Hi! I just wanted to point out that at 12:23 you have a cycle in the graph.
By the way, these videos is great at explaining these algorithms.
Oh I saw that Dijkstra's algorithm works on Directed Acyclic Graphs so I thought that was a requirement.
It turns out that the only requirement is edge weights are non-negative.
thanks a lot sir
can we use ordered_map for this eagers implementation?
I would love to see a video on Fibonacci Heap and its applications in Dijkstra's. Please make a video on it.
Hey. I have a question at 14:53. Lets assume we start at node s. We travel to some nodes and realize that we found the "end" of the path we wanted to find. Wouldnt that mean i had to check all nodes for their cost that point to e? I'm confused since as far as i understand the only node tuple i save in the PQ is the ones my prev could visit. But what if my prev didnt have the chance to visit it yet?
Suppose an unvisited node i has a lower cost to visit e, then we have c_ie + dist_i < dist_e, which means dist_i < dist_e. If this happens, we must choose node i from the PQ instead of e.
I there a link to javascript/python code as shown in slides (instead of java)?
@WilliamFiset: For lazy implementation, instead of checking whether if (dist[node.id] < node.value) continue; can't we just check if we had already visited the node and skip it if so?
Yes I have the same doubt as well.12:05
Same thought occurred to me and glad to see I'm not alone.
you already mark it as visited just before that check. I suppose that would work before you mark it visited
This would be in line to the fact stated at 01:38 that once a node is visited, its distance cannot be further improved
I don't understand that youtube channels like TechLead have 1M subscribers and this has just a few thousands. People are weird. Anyways superb content :)
I have implemented Fibonacci heap to solve SSSP using Dijkstra's Algorithm in my final semester in college, but yeah theoretically it gives a lower bound, and I haven't tested it's performance against any standard algorithm yet.
Nice, but the repo link doesn't seem to have the code from the video...
Hi, WilliamFiset. So, after watching the video, I have some concerns with Dijkstra's algorithm. Primarily, is the concern that in some configurations of edge costs, certain nodes may not be reached or, at least, sensibly (Dijkstra's algorithm may yield a nonsensical result) reached with the algorithm. Also, the fact that these graphs use directed edges may complicate the problem further. Dijkstra's algorithm does not look more than one step ahead to find the most optimal path in the current step. It calculates the closest node to it in one instance and advances down the path that includes all the closest path relative to it. But what if, later down the road, it is discovered that the path that Dijkstra's algorithm was advancing down was not the most optimal path after all.
This particularly becomes a problem when considering that there are several guards we put in place to prevent backtracking in this implementation (e.g. not visiting previously nodes and utilizing directed edges). If we take the shortest path relative to a node in that instance and later discover that the path we took has a greater cost than another previous one, how do we account for that? We may not even be able to advance from the current node at all if that node doesn't have any outwards edges. Dijkstra's algorithm doesn't really calculate if the path it is traversing will lead to a dead end or if previous nodes can be re-reached.
Using the graph at around the 16:26 - 19:27 time mark for reference, at the step where we add node 4 with an edge cost of 13 to the distance array, we go on to later advance to the step where node 4 is updated with a best-distance of 9, since the edge cost from node 3 to node 4 is 2. But what if that edge cost was something outrageous like 100? In this instance, the best distance to 4 and consequently the most optimal path does not lie on the current path. In fact, this shows, at that step that we advanced to node 1 from node 2 instead of to node 4 from node 2, we should have done the opposite. But, as far as I can tell, there is no way to do that with this algorithm. Once you've visited a node you can't 'unvisit' or revisit it.
So in one run of Dijkstra's algorithm, following this configuration of edge costs, the algorithm has yielded the wrong result because either the algorithm will still try to complete the path from node 2 to node 4, which is synonymous to jumping from one position in the graph to another non-adjacent position, and doesn't make sense or it will not take the path from node 3 to node 4 because it sees the best distance to that node as 13, and then node 4 will never be visited.
Am I correct in my formulation? Is there some workaround for this pitfall besides not using Dijkstra's or does Dijkstra's algorithm require some additional conditions like the edge costs following some logical ordering? Thank you!
A bit late maybe, but at 17:45 you can see that the lowest value to reach node 4 is 13, namely getting there from node 2. That means that if the cost from 3 to 4 would have been outrageous, then you're right and the option of getting to 4 through 2 would have been best and the algorithm would come to that same conclusion when encountering the outrageous value. It's not that it 'unvisits' or revisits a node: it just keeps the then-best path in mind (along with the node on it), and figures out if it can find a better one.
In other words, I think the trick to Dijkstra is that it keeps all the current best candidates in an array ("dist" in this case), and only updates a candidate if it finds a better way to get there. Any 'outrageous' value on the current best path would simply cause Dijkstra to devise another best path based on the current optimal values to get to the nodes. Here someone answers what I think is basically the same question by saying "it's not greedy": math.stackexchange.com/questions/352097/dijkstras-algorithm-does-not-work
Does any of that help, despite the poor timing?
Now that I'm commenting anyway: An infinite amount of thanks to @WilliamFiset for these videos by the way :)
Abietarius Thank you. Sorry for my late response too. I think I had Dijkstra’s algorithm confused with a minimum spanning tree algorithm. Dijkstra’s algorithm does not find the optimal continuous path that spans all nodes. It finds the best path to any particular node. That may or may not span multiple nodes. It depends on the edge costs and the orientation of the graph. That’s where I was confused. Dijkstra’s algorithm allows jumps because the optimal path to a particular node may lie on a different path than what we were originally taking. Dijkstra’s only ensures that we process the next most promising edge in the order that they are weighted, which allows us to always construct the optimal path between nodes.
@@kingdominth4 this is correct!! I was confused with this too since I learned minimum spanning tree first. I hope more people see your comment.
I think Advent of code 2023 day 17 puzzle is a perfect example to your concern with maximum 3 consecutive moves as the key constraint to make current optimal path become sub-optimal path later on and we have no way to go back with traditional Dijkstra algorithm.
"This particularly becomes a problem when considering that there are several guards we put in place to prevent backtracking in this implementation (e.g. not visiting previously nodes and utilizing directed edges). If we take the shortest path relative to a node in that instance and later discover that the path we took has a greater cost than another previous one, how do we account for that? We may not even be able to advance from the current node at all if that node doesn't have any outwards edges. Dijkstra's algorithm doesn't really calculate if the path it is traversing will lead to a dead end or if previous nodes can be re-reached."
Videos are really helpful, but just a little feedback, I get confused everytime you use 'relax' or 'relaxation'
It is actually a common thing to say when we improve a path. Thats what you'll see in most books.
@9:15 I don't think we need the visited array.
We are using the visited array to make sure that we aren't inserting a node into the priority queue if it's shortest path has already been found.
But we can achieve the same functionality without using the visited array.
This because if an element is visited then we have already found it's shortest path. ( MinDistance)
So instead of maintaining a visited array can just check whether the new distance is less than the one we already have in the dist array.
This is something we are already doing, so I think even without the visited array we won't insert the node if it's shortest path has already been found.
Is my understanding correct??
I think the visited array is still needed. Because "the new distance is less than the one we already have in the dist array" doesn't mean the new distance is the minimum yet. For example, on a graph represented in this format (from, to, cost): (A, B, 1), (A, C, 8), (B, C, 10), (B, D, 2), (D, C, 3). When B's visited (popped from Q), C's current dist (from A) is 8, while new dist (from B) is 1+10=11. So for C, at this moment "the new distance is less than the one we already have in the dist array", and C will be marked visited. However, the actual min dist of C (from D) is 1+2+3=6, which won't be updated if it's already been marked visited previously.
@@kaze3311 The idea is that everytime we find a path to a node, we check if it's cost is less than the one we already have, if yes then we push it into the Priority Queue. If not then we simply don't push it.
If we find a path which is more expensive than the one we already have, we don't mark the node as visited, we simply don't push it in Priority Queue, so if we find the actual shortest path later on it will be considered as it's cost will be less than the value we already have.
@@rahulas721 Yes I think you're right! The purpose of the visited array is simply to avoid adding a (visited) node's edges again and again. But this endless adding can be avoided by comparing the new distance (dist of currently popped node + weight of edge) against the dist array record as you mentioned above, so the visited array is no longer needed. I think my previous comment was mixing the 2 operations: checking visited array vs updating the dist array. Thanks for the explanation!
12:58 I think you forgot to make clear that when we're implementing we should pass the distance FIRST and then the node index because if we do the way its in the video its gonna fail for this test:
0 -> [{1, 10000}, {2,1}]
1 -> [{2, 10}]
2 -> [{1, 10}]
S = 0
So you either need to make a custom comparator for the priority queue or you should use the distance first and the index second: pq.insert((0, s)) instead of pq.insert((s, 0))
I do not understand. How is it different from usual DFS?
I guess, Dijkstra's uses BFS to find Shortest path.
I solved dijkstra's without using vector vis(n,false) it works the same... Any comment on that???
You can visit a node later again, but you will compulsarily have higher distance than what you got earlier so no relaxations happen and it doesn't change your answer. You can reduce that unecessary work by not visiting visited nodes again.
r u the one in brackhys videos?
can i get these slides please
Basic question, but which language is this? Look like python but not exactly
Prabhu! Why didn't I find you earlier?
u should see if vertex is visited before the for statement not inside it
Man, you are legend! it's my third video on your channel about graphs and everything is super easy to learn. I use you videos to complete Graph course on leetcode because their videos are shit
best
Your video makes me Sleep.
Just kidding.
Thank you
do i have to understand d-ary heaps for interviews or is it fine if i just understand the Eager Dijkstra's algorithm?
“built in priority queue” lol said the people making C
It can be better if he label the vertices as a,b,c ...in stead of 1, 2 made confused with the edge weigh .
Agreed, although thinking about nodes as numbers becomes handy when you start implementing this in code :)
3:50
Why do you need list visited for finding a less cost path? Your algorithm never checks next node with a better path that has been visited...Algorithm ouputs the path with nodes that are visited first. I can't see no greed here :)
cycle detection
super confusing.
meg akarok halni
Well you did not talk about correctness at all.
g, n, s, e
Wow these are one of the worst var names ever made.