Implement Dijkstra's Algorithm

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

[@NeetCodeIO]

You can implement Dijkstra's algorithm yourself here: neetcode.io/problems/dijkstra
Got a lot more coming to neetcode io! 🚀🚀

[@sumitsharma6738]

@@anonforever123 like ...

[@m.kamalali]

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

[@anshror2583]

Bro please create a playlist on your channel

[@nyosgomboc2392]

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.

[@KostasPagratis]

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?

[@ronbuchanan5432]

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

[@atomatopia1]

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.

[@KrzysztofKoziarski]

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'

[@tubero911]

The example 1 graph visual at 1:00 does not match the subsequent input of the number of vertices (n) and the edges.

[@waelmas]

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

[@alexleibowitz6448]

thank you -- i think the above implementation does not seem quite right either

[@sumanthanumula8048]

This will give you negative edges as well correct ? I mean Dijkstra asked us not to visit already relaxed nodes, didn't he?

[@alexleibowitz6448]

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?

[@sumitsharma6738]

In a couple of months neetcode will start it's own fang company 😂

[@21centuryschizoid]

error in line 8 the weight and the destination should be reversed

[@jorgeramongonzalezozorno7755]

Hi, could you consider making a video about the travelling salesman problem

[@jagannthaja7904]

My goodness more of these please!
Do u have any plans on releasing dsa course in udemy?
I would easily buy it.

[@infoknow3278]

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?

[@jritzeku]

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

[@sumitsharma6738]

Great Video 🙂

[@akash-kumar737]

Didn't liked it. I probably prefer detailed approach rather than directly coding.

[@CrustyMusty101]

There’s a video for each purpose. This one is for the actual implementation (as it says in the actual title), which means code.
There’s a video from a channel called Spanning Tree called titled “How Dijkstra algorithm works” which has a short and very understandable explanation of the algorithm with zero code.

[@appi147]

@@CrustyMusty101 Yeah that video is amazing. In this video, implementation differs a bit.
th-cam.com/video/EFg3u_E6eHU/w-d-xo.html

[@FrenchFries196]

Now this is content

[@infoknow3278]

❤❤

[@Fam-m4i]

This is not Dijkstra for sure .

[@daydrivver2074]

This is an awful video not on the neetcode level, not a single explanation why just copy pasting code.