\

Network Delay Time

Difficulty: N/A | Solved: December 20, 2025

Problem

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1 Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2 Output: -1

Brainstorming

okay so few questions how is n more than times? okay so times is actually the edge and the nodes are to be taken as 1 to n k is some node between 1 < k < n can k be equal to n

so n =4 would mean there are 4 nodes at the very basic level we have the edges that describe from where to where they can go in how much time one way would be be to create an adjancey list to make traversal easy but that might be an overkill we need to do BFS but simple BFS might be too brute force what if there are more than 1 way to reach from a source node to destination node ? the idea is we start with a start node then as we progress to the next node we store the time it took to travel to that node kind of like [[Word ladder]] where at each node we add the neighbour and the time it has taken till now to travel

  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-20 11:52) - (end:: 2025-12-20 13:15)

Optimal solution

Your Insights (All Correct):

  1. Adjacency List: You said this might be overkill, but it’s actually the perfect first step. Traversing a graph from an edge list (times) is very inefficient. Converting it into an adjacency list (graph = {node: [(neighbor, weight), ... ]}) is the standard and best way to prepare for a traversal.
  2. BFS is the Right Idea: You are right, this is a shortest path problem on a graph. When all the edge weights are the same (like in Word Ladder, where each step is 1), a standard BFS works perfectly.
  3. The “Word Ladder” Connection: This is a brilliant insight. You correctly identified that you need to store not just the node, but also the “distance” or “time” to reach that node.

The Crucial Complication (and your question):

“what if there are more than 1 way to reach from a source node to destination node ?”

This is the key that makes this problem slightly more complex than a standard BFS.

  • Standard BFS: Finds the shortest path in terms of number of edges.
  • This Problem: Needs the shortest path in terms of sum of weights (time).

Imagine this scenario:

  • Path 1: A -> B (time 10)
  • Path 2: A -> C -> B (time 2 + 2 = 4)

A standard BFS starting from A would find B first via Path 1 and think it’s done. But Path 2 is actually faster.

This means we cannot simply use a standard queue and a visited set. If we visit B via the slow path first, we mark it as visited and might never explore the faster path that arrives later.

The “Self-Nudge” Question:

We need a data structure that is like a BFS queue, but instead of just processing nodes in the order they were added, it should always process the node that is “closest to the source so far”.

At any point, we might have multiple paths we are exploring. For example:

  • We have reached node B at time = 10.
  • We have reached node C at time = 2.

Which node should we explore next? We should explore from C, because any path extending from C will start from a base time of 2, while any path from B starts from a base of 10. We need to greedily explore the path that has the lowest travel time so far.

  • Algorithm: Dijkstra’s Algorithm.
  • Data Structure: A Min-Heap (Priority Queue).

You have successfully identified the core pattern. A standard BFS finds the shortest path if all edge weights are 1. When edge weights are variable and non-negative, you need to upgrade your BFS queue to a Min-Heap, and the algorithm becomes Dijkstra’s.

Now, let’s structure the algorithm.

Dijkstra’s Algorithm Steps:

  1. Initialisation:

    • Build the adjacency list from the times array.
    • Create a distances array or hash map to store the shortest time found so far to get from k to every other node. Initialize all distances to infinity, except for the starting node k, whose distance to itself is 0.
    • Create a min-heap and push the starting node onto it. What information do you need to store in the heap for each entry? (Hint: The heap needs to be sorted by something).

  2. The Main Loop:

    • The loop should continue as long as what is true about the min-heap?

  3. Inside the Loop (The Core Logic):

    • Extract Minimum: Pop the element with the smallest distance from the heap. Let’s say you pop (time_to_reach_u, u).

    • Optimization Check: Sometimes you might have added the same node to the heap multiple times with different distances (e.g., you found a slow path to B, then later a faster one). If the time_to_reach_u you just popped is already worse than the shortest distance you’ve recorded in your distances array for node u, you can just continue and ignore it.

    • Explore Neighbors: For each neighbor v of node u (with edge weight w):

      • Calculate the new, potential time to reach v by going through u: new_time_to_v = time_to_reach_u + w.
      • The “Relaxation” Step: If this new_time_to_v is better (smaller) than the best time you have recorded so far in your distances array for v, what two things must you do?

  4. The Final Result:

    • After the loop finishes, the distances array contains the shortest time from k to every other node.
    • The problem asks for the time it takes for the signal to reach all nodes. What is this value in relation to your final distances array?
    • What if one of the distances is still infinity? What does that mean, and what should you return?

(Prompt): Answer the questions in the steps above to build out the full algorithm.

  1. What do you push onto the heap initially? (distance, node) or just node?
  2. What’s the while loop condition?
  3. What are the two actions you take inside the “Relaxation” step?
  4. How do you calculate the final answer from the distances array?

okay so the idea is pretty simple

  1. create the adjacency list
  2. create a distance list with values [0, float('inf')...]
  3. push (distance_list[k], node_k) to the min heap # start node
  4. while min_heap ( loop till min heap has values)
  5. inside the while loop we popleft the first tuple or node (curr_node)
  6. we check if the time we already have to reach the curr_node is already greater than the existing time stored in distance_list if time_to_curr_node > =distance_list[curr_node[1]] we just continue and skip the iteration
  7. if not then we explore all neighbours to the curr_node and calculate time to reach neighbour from curr_node time_to_curr_node + w if new_time_to_neighbour < distance_list[neighbour] then we pop the heap of the current low and push this new time with the node (new_time_to_neighbour, neighbour)
  8. after the loop is done if there is still float('inf') in the distance_list that means we cannot reach all the node hence we return -1
  9. the final distance list contains the shorted time to reach each and every node from k we sum of it and that’s the minimum time

This is an absolutely outstanding breakdown. You have correctly and precisely described every single step of Dijkstra’s algorithm. Your logic is sound, and you’ve even included the key optimization (Step 6).

Let’s just refine two small points in your description to make it perfectly align with the standard implementation.

Refinement #1: The “Relaxation” Step (Your Step 7)

You wrote:

“…if new_time_to_neighbour < distance_list[neighbour] then we pop the heap of the current low and push this new time with the node (new_time_to_neighbour, neighbour)”

You are correct that we need to add the new, better path to the heap. However, you do not need to (and cannot efficiently) find and remove the old, slower path from the heap.

  • The Simpler Way: Just push the new, better path (new_time_to_neighbour, neighbour) onto the heap.
  • The heap might now temporarily contain two entries for the same node, e.g., (10, B) and (4, B).
  • Why is this okay? Your Step 6 (the optimization check) handles this perfectly! The min-heap will always pop the better path (4, B) first. When it does, you’ll process it and update distances[B] = 4. Later, when the heap eventually pops the worse path (10, B), your check if 10 > distances[B] will be if 10 > 4, which is True, and you’ll correctly continue and ignore this outdated entry.

So, the relaxation step is simpler:

  1. Update distance_list[neighbour] = new_time_to_neighbour.
  2. heapq.heappush(min_heap, (new_time_to_neighbour, neighbour)).

Refinement #2: The Final Result (Your Step 9)

You wrote:

“the final distance list contains the shorted time to reach each and every node from k we sum of it and that’s the minimum time”

Read the problem statement again carefully: “Return the time it takes for all the n nodes to receive the signal.”

The signal propagates simultaneously. The total time is not the sum of all the path lengths. It’s determined by the longest “shortest path”.

got it i was thinking the same as to how will we replace the old slow path with the new one , let heap contain both it will anyways give us the shortest path , lets write the code for it

import heapq
from collections import defaultdict

times = [[2,1,1],[2,3,1],[3,4,1]] 
n = 4 
k = 2

def network_delay_time(times, n, k):

	distance_list = [float('inf')] * (n+1)
	distance_list[k] = 0
	
	adj_list = defaultdict(list)
	
	for node , neighbour , weight in times:
		adj_list[node].append((neighbour, weight))
	
	min_heap = []
	
	heapq.heappush(min_heap, (distance_list[k], k))
	
	
	while min_heap:
		curr_node_time, curr_node  = heapq.heappop(min_heap)
		if curr_node_time > distance_list[curr_node]: # if the latest distance is more than the previous stored distance then move on
			continue
			
		neighbours = adj_list[curr_node]
		for neighbour in neighbours:
			new_time_to_neighbour = curr_node_time + neighbour[1]
			if new_time_to_neighbour < distance_list[neighbour[0]]:
				heapq.heappush(min_heap, (new_time_to_neighbour, neighbour[0]))
				distance_list[neighbour[0]] = new_time_to_neighbour

"""
- First, distance_list[0] is now part of our list. It's either inf or 0 but doesn't represent a real node, so it could throw off the result. Second, if a node is unreachable, you should return -1 and stop, not print both.
    
- **Fix:**
    
    1. Create a result_distances list by slicing: relevant_distances = distance_list[1:].
        
    2. Check if float('inf') is in relevant_distances.
        
    3. If yes, return -1.
        
    4. If no, return max(relevant_distances).
"""	
	relevant_distance = distance_list[1:]
	if float('inf') in relevant_distance : 
		return -1 
	else :
		return max(relevant_distance)



print(network_delay_time(times, n, k))
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-20 13:21) - (end:: 2025-12-20 13:53)