Network Delay Time - Dijkstra's algorithm - Leetcode 743

0:00 - Read the problem
4:37 - Drawing Explanation
14:37 - Coding Explanation

leetcode 743

#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[emmanuel]

I like the fact that you mention that it is indeed difficult and you also came across lot of bugs while writing this code. It makes us feel we are not the only ones struggling. Conducive to learning!

[saisurya]

I ran the same code but instead of 't = max(t, w1)'; I just put 't = w1'. It worked with all test cases passing. That max() operation felt redundant, I broke my head trying to understand why we needed it in the first place. Then I tried omitting it myself and it worked. Also, it was faster by 200 ms this way. Anyways, I really appreciate your solution. Thanks Neetcode!

[jonaskhanwald]

Bellman ford solution:
(n-1 iterations. Stop iterating, if none of the value changes from the prev iteration)

class Solution:
def networkDelayTime(self, a: List[List[int]], n: int, k: int) -> int:
#Bellman Ford
dp = [float("inf") for i in range(n+1)]
dp[k]=0
dp[0]=0
stop = True
j = 0

while j < n-1 or stop:
stop = False
for i in range(len(a)):
src = a[i][0]
dest = a[i][1]
wt = a[i][2]
if dp[dest] > min(dp[dest], dp[src]+wt) :
dp[dest] = min(dp[dest], dp[src]+wt)
stop = True
j+=1
print(dp)
if max(dp)==float("inf"):
return -1
else:
return max(dp)

[shreza]

Just wanted to say thanks, I don’t know how and why I understand all your solutions in the first go itself which i can never say about the actual Leetcode premium solutions or others in the discussion section

[PippyPappyPatterson]

Regarding complexity analysis—
Since the number of edges `E` is given as an argmuent (`times`), what was the motivation for analyzing the algorithm in terms of `E` and `V` instead of just E (`E * log(E)`) or just V (`V ** 2 * log(V`)?

[karthikmurali]

This entire algorithm has been explained in detail. After watching, you can clearly understand the Dijkstra's algorithm and apply it to the problem. Thanks!!

[venkatasundararaman]

Actually we can add few optimizations to this code.
1) We can stop the while loop when the visit set reaches n. Reason: since we are using a minHeap we are ensured to get the minimum path to all nodes and we can stop once we have reached all the nodes.
2) Also we can remove the continue block as we are checking if a node is in visit set before adding it to the minHeap.

class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adjList = {i:[] for i in range(1, n+1)}

for u, v, w in times:
adjList[u].append((v, w))

time = 0
minHeap = [(0, k)]
visit = set()

while minHeap and len(visit) < n:
w1, n1 = heapq.heappop(minHeap)

visit.add(n1)
time = max(time, w1)

for n2, w2 in adjList[n1]:
if n2 not in visit:
heapq.heappush(minHeap, (w1+w2, n2))

return time if len(visit) == n else -1

After adding these optimizations, the runtime decreased by 300ms for me.

[omuralievbaurzhan]

Hey, bro!

I am just loving what you do, thanks a lot!

It will be nice to mention why the order of values in minHeap must be in this exact order(weight, node). Due, to how minHeap in python works, it will order heap objects by the first value(weight). If you place values the other way (node, weight) --> It will work wrong.

[janmejayadas]

Why is max(t, w) required. Since we don't visit already visited node and no negative time value, won't the new value from minHeap be always greater than t?

[cutiex]

I've been calling it [D ai ks tra] throughout uni!!😆Love the algo thank you for the detailed explanation!

[whatuphere]

nav you were right, i got the intuition by myself but had a lot of confusion writing the algorithm.

[bestsaurabh]

7:16 Getting minimum from min-heap is not log(N) but O(1).

[Eckkbert]

As always, nice explanation :) I think you could omit the t variable and use w1 instead in the return statement, since the last w1 will be the solution. So instead of t = 0, we could do w1 = 0 before the loop.

[Sulerhy]

I am not graduated from CS, this is the first time I know Dijkstra's algorithm. Thank you so much for your explaination

[sunginjung]

thanks for the great video, what is the reason for t = max(t, w1)? dont we want the shorter time? shouldn't it be min(t, w1)? I am confused lol

[sunillama]

the course dijkstra's solution was more than sufficient. Thank you

class Solution(object):
def networkDelayTime(self, times, n, k):
adj = {}

for n in range(1, n+1):
adj[n] = []

for s, d, w in times:
adj[s].append((d, w))

shortest = {}
min_heap = [(0, k)]

while min_heap:
w1, n1 = heapq.heappop(min_heap)

if n1 in shortest:
continue

shortest[n1] = w1

for ne, w in adj[n1]:
if ne not in shortest:
heapq.heappush(min_heap, (w+w1, ne))

return -1 if len(shortest)!=n else max(shortest.values())

[danny]

In the official leetcode solution, BFS was used with time complexity of O(V+E). How come BFS is more optimal than dijkstra's approach which has time complexity of O(V + ElogV)?

[jritzeku]

The examples provided thus far are not addressing the case when there are simultaneous routes to shortest path. Although
it works and passes, not sure how the code addresses following case.

ex:
[[1, 2, 1], [2, 3, 2], [1, 3, 2]]

output: 3 ; you would think this is answer since resulted from 1->2(weight1), then 1->3(weight2)
expect: 2 ; since 1->2 and 1->3 is happening simultaneously, the weight 2 is picked.

[ramvenkatachalam]

U r a God bro. super videos and easy to understand . super bro . super.

[jugsma]

wow, hat's off to Neetcode. This is way to complicated problem, you solved it so perfectly. Thanks