Implement Dijkstra's Algorithm
HTML-код
- Опубликовано: 9 фев 2025
- Implement Dijkstra's shortest path algorithm yourself here: neetcode.io/pr...
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
#neetcode #leetcode #python
You can implement Dijkstra's algorithm yourself here: neetcode.io/problems/dijkstra
Got a lot more coming to neetcode io! 🚀🚀
@@anonforever123 like ...
Bro please create a playlist on your channel
In this approch you add nodes in queue more times than needed
If you have node in q and you get new value for this node you add it even the prev one has less cost
To avoid this you can node into q if it leeds to less cost
You are doing a great job. I'm so happy I bought lifetime access.
I hope you will add more topics to 'Advanced Algorithms' and 'System Design Interviews'
In a couple of months neetcode will start it's own fang company 😂
Not an expert, but I felt like this solution does not seem to follow the typical definition of the algorithm? Might be wrong as this is the first video from @NeetCodeIO that did not feel very accurate. (Love your channel btw)
class Solution:
def shortestPath(self, n: int, edges: List[List[int]], src: int) -> Dict[int, int]:
# Create adjacency list
adj = {i: [] for i in range(n)}
for s, d, w in edges:
adj[s].append((d, w))
# Map of shortest paths from source to node
# More correct Dijkstras approach: Initialize with inf
shortest = {i: float('inf') for i in range(n)}
shortest[src] = 0
# Priority queue to explore nodes, starting from source
minHeap = [(0, src)] # (weight, node)
while minHeap:
w1, n1 = heapq.heappop(minHeap)
# Only proceed if the current path is still relevant
if w1 > shortest[n1]:
continue
for n2, w2 in adj[n1]:
new_dist = w1 + w2
if new_dist < shortest[n2]:
shortest[n2] = new_dist
heapq.heappush(minHeap, (new_dist, n2))
# Check for any nodes that were not reachable
for i in range(n):
if shortest[i] == float("inf"):
shortest[i] = -1
return shortest
thank you -- i think the above implementation does not seem quite right either
This will give you negative edges as well correct ? I mean Dijkstra asked us not to visit already relaxed nodes, didn't he?
What specifically is wrong with my approach? If a node is visited we skip it with the continue anyway. DIjkstra's is greedy, the first time you visit a node it must be the shortest path.
The example 1 graph visual at 1:00 does not match the subsequent input of the number of vertices (n) and the edges.
the implementation you read about in algo textbooks always talk about updating the queue. I guess if a node was already on the queue but unvisited and with a longer distance, it would just be crowded out by the new version with shorter distance?
Am I missing the case where there are multiple paths to the same node. Shouldn't there be a check around if i have a path already and it's longer than the current path, replace?
Yeah, I'm confused too. I asked ChatGPT/Gemini to implement their own version of Dijkstra and you can see the difference
ChatGPT did this check
if current_dist > distances[current_node]:
continue
I believe that the minheap will always sort the input routes by total weight and only pop the shortest route that has been seen. If there's a longer route, it just lingers at the bottom of the minheap and the code exits the heap segment before popping off the longer (unnecessary) routes.
It will only ever look at the first and shortest route to any adjacent nodes. It's not a breadth first search by virtue of visiting each adjacent node first, it's a breadth first search by virtue of visiting each adjacent shortest path. If there are 2 paths of nodes where the first path is all connected with weights of 1 and the second route is all connected with weights of 3, it will visit 3 nodes of the first route before visiting the first node of the second route. This is called being "greedy"
I don't know if this is a true implementation of Dijkstra's Algo, because I think Dijkstra's visits each neighbor first and keeps a record of the shortest paths to each adjacent node as it traverses more adjacent nodes.
Edit: It seems like this is a true implementation of Dijkstra's algo, there are just multiple ways people explain it and some are less clear than others.
There won't ever be a shortest path where it needs to be replaced. Whatever nodes that are already inside the shortest path are indeed the shortest path, so if you do find another path leading to that node it will always be longer than the shortest path. This of course assumes the weights are non-negative.
Being a greedy algorithm you don’t need to check for multiple paths since we want the shortest the min heap will return the shortest path at any given point. You can check out the proof of induction as to why the greediness works
To be honest, I am confused about the graph part in 1:18. Seems like your talk and the animation is not sync
Hey amazing job! Could you also create task with A* algorithm?
its 3 am, i am not a programmer. what am i doing here? good video btw, i could still follow it even tough i have 0 programming knowledge
Hi, could you consider making a video about the travelling salesman problem
This code solves the problem and answers the shortest path to all those nodes. But is this Dijkstra? It looks like a different algorithm.
Dijkstra loops through the unvisited nodes in the shortest path order, yours uses a BFS.
Great Video 🙂
My goodness more of these please!
Do u have any plans on releasing dsa course in udemy?
I would easily buy it.
Bhaiya i have a question , Need your advice I have started dsa solved 200+ but when again I visited on the problems I forgot 50 to 60 percent logic
But I know how I approached if I stuck i see ur videos it helps me a lot ..
How to overcome that?
1.) Really focus on the algorithms per each data structure. IF u know this, u have the tools to solve any problem.
Arrays - sliding window, two pointer, freq. counter(hashmap) , recursion
Graphs - dfs, bfs, dijkstra, disjoint set etc.
Trees , Linked lists -traversals, insertions...etc
2.) Write pseudo code for each of the above algorithms because that is MUCH easier to remember than
specific code. Also, for pseudo code, write at different level (least detail to most detail). Generally the least detail
is easiest to remember.
When you see a problem and are able to identify which algorithm is needed, IMMEDIATELY write the sudo code via
comments. Then u can get to code later.
ex: Imagine we got problem to find shortest dist for a source to other node . We immediately write
djikstra sudo code(moderately detailed). Then from then, u can write your code.
-STEP1: Set up: adjList, minHeap, shortestPath(map/obj)
-STEP2: perform bfs
->if already in shortestPath skip
->if not in shortestPath, add to it
->when exploring neighbors, relax edges as needed (updating minHeap)
-STEP3: for unvisited nodes, set to -1
error in line 8 the weight and the destination should be reversed
Now this is content
❤❤
This is not Dijkstra for sure .
This code is wrong.
what specifically?