Implement Dijkstra's Algorithm

#neetcode #leetcode #python

[NeetCodeIO]

Got a lot more coming to neetcode io! 🚀🚀

[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

[nyosgomboc]

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.

[anshror]

Bro please create a playlist on your channel

[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?

[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

[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'

[sumitsharma]

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

[tubero]

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

[alexleibowitz]

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?

[centuryschizoid]

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

[jagannthaja]

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

[jorgeramongonzalezozorno]

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

[infoknow]

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?

[akash-kumar]

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

[daydrivver]

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