LeetCode 743 - Network Delay Time

This problem models a directed weighted graph. Each node represents a computer in the network, and each directed edge represents the time required for a signal to travel from one node to another.

leetcodemediumdepth-first-searchbreadth-first-searchgraph-theoryheap-(priority-queue)shortest-path

LeetCode Problem 743

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

This problem models a directed weighted graph. Each node represents a computer in the network, and each directed edge represents the time required for a signal to travel from one node to another.

The input times contains edges in the format:

(ui, vi, wi)

where:

  • ui is the source node
  • vi is the destination node
  • wi is the travel time from ui to vi

The graph is directed, which means a signal can travel from ui to vi, but not necessarily in the reverse direction.

We start sending a signal from node k. The task is to determine how long it takes for every node in the graph to receive the signal. Since signals can travel through intermediate nodes, we are really looking for the shortest travel time from k to every other node.

If every node is reachable, the answer is the maximum shortest-path distance among all nodes. This is because the last node to receive the signal determines the total delay time.

If at least one node cannot be reached from k, then the signal never reaches the entire network, so we return -1.

The constraints are important:

  • n <= 100, so the graph is relatively small
  • times.length <= 6000, meaning the graph can still be fairly dense
  • Edge weights are non-negative, 0 <= wi <= 100

The non-negative edge weights are the key observation. Whenever we need shortest paths in a graph with non-negative weights, Dijkstra's algorithm becomes a natural fit.

Several edge cases are important:

  • Some nodes may be disconnected from the starting node
  • The graph may contain cycles
  • Edge weights may be zero
  • There may be only one node in the graph
  • The starting node may not have outgoing edges

The problem guarantees there are no duplicate directed edges between the same pair of nodes, which simplifies graph construction.

Approaches

Brute Force Approach

A brute-force solution would repeatedly relax every edge until no shorter distances can be found. This is essentially the Bellman-Ford algorithm.

We initialize the distance to the starting node as 0 and all other nodes as infinity. Then we repeatedly scan all edges and attempt to improve distances.

For every edge (u, v, w):

distance[v] = min(distance[v], distance[u] + w)

After at most n - 1 passes, all shortest paths are guaranteed to be computed.

This approach is correct because the shortest path between two nodes can contain at most n - 1 edges. Repeated relaxation eventually propagates the optimal distances through the graph.

However, this solution is inefficient because it processes all edges repeatedly, even when most distances have already stabilized.

Optimal Approach

The key insight is that all edge weights are non-negative. This allows us to use Dijkstra's algorithm.

Dijkstra's algorithm always expands the currently closest unvisited node first. Once a node is removed from the priority queue with the smallest distance, we know its shortest path is finalized.

To efficiently retrieve the next closest node, we use a min-heap, also called a priority queue.

The algorithm works as follows:

  1. Build an adjacency list representation of the graph
  2. Store shortest known distances from k
  3. Use a min-heap ordered by current distance
  4. Repeatedly process the node with the smallest known distance
  5. Relax all outgoing edges

This avoids unnecessary repeated scans of the entire edge list and significantly improves performance.

Approach Time Complexity Space Complexity Notes
Brute Force O(V × E) O(V) Bellman-Ford style repeated edge relaxation
Optimal O((V + E) log V) O(V + E) Dijkstra with adjacency list and min-heap

Algorithm Walkthrough

  1. Build an adjacency list from the input edges.

We convert the edge list into a graph representation where each node maps to its outgoing neighbors. This allows efficient traversal of adjacent nodes during the algorithm.

Example structure:

graph[2] = [(1, 1), (3, 1)]

This means node 2 has edges:

  • 2 -> 1 with weight 1
  • 2 -> 3 with weight 1
  1. Initialize the shortest distance array.

We store the shortest known time from k to every node.

Initially:

  • distance[k] = 0
  • all other distances are infinity

Infinity represents nodes that have not yet been reached. 3. Create a min-heap priority queue.

Each heap entry stores:

(current_distance, node)

The heap ensures we always process the node with the smallest known distance next. 4. Start processing nodes from the heap.

Repeatedly remove the smallest-distance node.

If the popped distance is already larger than the stored shortest distance, we skip it because a better path was already discovered earlier. 5. Relax all outgoing edges.

For every neighbor:

new_distance = current_distance + edge_weight

If this new path is shorter than the currently known distance, update it and push the new state into the heap. 6. Continue until the heap becomes empty.

At this point, all reachable shortest paths have been finalized. 7. Compute the final answer.

If any node still has infinite distance, return -1.

Otherwise, return the maximum value in the distance array because the last node to receive the signal determines the total delay time.

Why it works

Dijkstra's algorithm relies on the property that edge weights are non-negative. When a node is removed from the min-heap, it is guaranteed to have the smallest possible shortest-path distance among all unprocessed nodes.

Because any future path would only add non-negative weights, no later path can produce a smaller distance for that node. Therefore, each finalized distance is correct.

By repeatedly relaxing edges in increasing distance order, the algorithm computes the true shortest path from k to every reachable node.

Python Solution

from typing import List
import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)

        # Build adjacency list
        for source, target, weight in times:
            graph[source].append((target, weight))

        # Initialize distances
        distances = [float("inf")] * (n + 1)
        distances[k] = 0

        # Min-heap: (distance, node)
        min_heap = [(0, k)]

        while min_heap:
            current_distance, node = heapq.heappop(min_heap)

            # Skip outdated heap entries
            if current_distance > distances[node]:
                continue

            # Relax neighboring edges
            for neighbor, weight in graph[node]:
                new_distance = current_distance + weight

                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    heapq.heappush(
                        min_heap,
                        (new_distance, neighbor)
                    )

        max_distance = max(distances[1:])

        return max_distance if max_distance != float("inf") else -1

The implementation begins by constructing an adjacency list using defaultdict(list). This representation allows efficient access to all outgoing edges for a node.

The distances array stores the shortest known distance from the source node k to every other node. Index 0 is unused because the graph uses 1-based indexing.

The min-heap is initialized with (0, k) because the distance from the starting node to itself is zero.

Inside the main loop, we repeatedly pop the node with the smallest known distance. If the popped value is outdated, meaning a shorter path has already been discovered, we skip processing it.

For each neighbor, we compute a candidate shorter path. If the candidate improves the existing shortest distance, we update the array and push the new state into the heap.

Finally, we check whether every node was reached. If any distance remains infinity, we return -1. Otherwise, the maximum shortest-path distance is the total network delay time.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type Pair struct {
	node     int
	distance int
}

type MinHeap []Pair

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].distance < h[j].distance
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Pair))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func networkDelayTime(times [][]int, n int, k int) int {
	graph := make(map[int][][]int)

	// Build adjacency list
	for _, edge := range times {
		u := edge[0]
		v := edge[1]
		w := edge[2]

		graph[u] = append(graph[u], []int{v, w})
	}

	// Initialize distances
	distances := make([]int, n+1)

	for i := 1; i <= n; i++ {
		distances[i] = math.MaxInt32
	}

	distances[k] = 0

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	heap.Push(minHeap, Pair{
		node:     k,
		distance: 0,
	})

	for minHeap.Len() > 0 {
		current := heap.Pop(minHeap).(Pair)

		node := current.node
		currentDistance := current.distance

		// Skip outdated entries
		if currentDistance > distances[node] {
			continue
		}

		// Relax neighbors
		for _, neighbor := range graph[node] {
			nextNode := neighbor[0]
			weight := neighbor[1]

			newDistance := currentDistance + weight

			if newDistance < distances[nextNode] {
				distances[nextNode] = newDistance

				heap.Push(minHeap, Pair{
					node:     nextNode,
					distance: newDistance,
				})
			}
		}
	}

	maxDistance := 0

	for i := 1; i <= n; i++ {
		if distances[i] == math.MaxInt32 {
			return -1
		}

		if distances[i] > maxDistance {
			maxDistance = distances[i]
		}
	}

	return maxDistance
}

The Go implementation follows the same logic as the Python solution, but Go does not provide a built-in priority queue. Instead, we implement the heap.Interface from the container/heap package.

The adjacency list uses a map from node IDs to slices of neighbor-weight pairs.

Go does not have infinity values for integers, so math.MaxInt32 is used as a sentinel for unreachable nodes.

Unlike Python's tuple comparison behavior in heapq, Go requires explicitly defining heap ordering through the Less method.

Worked Examples

Example 1

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

Graph

2 -> 1 (1)
2 -> 3 (1)
3 -> 4 (1)

Initial State

Node Distance
1 inf
2 0
3 inf
4 inf

Heap:

Heap Contents
(0, 2)

Iteration 1

Pop:

(0, 2)

Process neighbors:

  • Node 1 gets distance 0 + 1 = 1
  • Node 3 gets distance 0 + 1 = 1

Updated distances:

Node Distance
1 1
2 0
3 1
4 inf

Heap:

Heap Contents
(1, 1), (1, 3)

Iteration 2

Pop:

(1, 1)

Node 1 has no outgoing edges.

Heap:

Heap Contents
(1, 3)

Iteration 3

Pop:

(1, 3)

Process neighbor:

  • Node 4 gets distance 1 + 1 = 2

Updated distances:

Node Distance
1 1
2 0
3 1
4 2

Heap:

Heap Contents
(2, 4)

Iteration 4

Pop:

(2, 4)

Node 4 has no outgoing edges.

Final distances:

Node Distance
1 1
2 0
3 1
4 2

Maximum distance is 2.

Answer:

2

Example 2

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

Initial State

Node Distance
1 0
2 inf

Process edge:

1 -> 2 (1)

Updated distances:

Node Distance
1 0
2 1

Maximum distance is 1.

Answer:

1

Example 3

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

Initial State

Node Distance
1 inf
2 0

Node 2 has no outgoing edges.

Final distances:

Node Distance
1 inf
2 0

Node 1 is unreachable.

Answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O((V + E) log V) Each heap operation costs log V, and edges are relaxed once
Space O(V + E) Adjacency list, heap, and distance array

The adjacency list stores every edge exactly once, requiring O(E) space. The distance array and heap together require O(V) space.

For time complexity, every node may be inserted into the heap multiple times, but each heap operation costs O(log V). Since each edge can trigger at most one successful relaxation, the overall complexity becomes O((V + E) log V).

Test Cases

from typing import List

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        import heapq
        from collections import defaultdict

        graph = defaultdict(list)

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

        distances = [float("inf")] * (n + 1)
        distances[k] = 0

        heap = [(0, k)]

        while heap:
            current_distance, node = heapq.heappop(heap)

            if current_distance > distances[node]:
                continue

            for neighbor, weight in graph[node]:
                new_distance = current_distance + weight

                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    heapq.heappush(
                        heap,
                        (new_distance, neighbor)
                    )

        max_distance = max(distances[1:])

        return max_distance if max_distance != float("inf") else -1

solution = Solution()

assert solution.networkDelayTime(
    [[2,1,1],[2,3,1],[3,4,1]],
    4,
    2
) == 2  # standard example

assert solution.networkDelayTime(
    [[1,2,1]],
    2,
    1
) == 1  # simple reachable graph

assert solution.networkDelayTime(
    [[1,2,1]],
    2,
    2
) == -1  # unreachable node

assert solution.networkDelayTime(
    [],
    1,
    1
) == 0  # single node graph

assert solution.networkDelayTime(
    [[1,2,0],[2,3,0]],
    3,
    1
) == 0  # zero-weight edges

assert solution.networkDelayTime(
    [[1,2,5],[1,3,2],[3,2,1]],
    3,
    1
) == 3  # indirect path shorter than direct path

assert solution.networkDelayTime(
    [[1,2,1],[2,1,3]],
    2,
    1
) == 1  # cycle in graph

assert solution.networkDelayTime(
    [[1,2,1],[2,3,2],[1,3,4]],
    3,
    1
) == 3  # shortest path through intermediate node

assert solution.networkDelayTime(
    [[1,2,1],[2,3,1],[3,4,1],[4,5,1]],
    5,
    1
) == 4  # long chain graph

assert solution.networkDelayTime(
    [[1,2,1],[1,3,1],[1,4,1]],
    4,
    1
) == 1  # star graph
Test Why
Standard sample input Validates basic correctness
Simple reachable graph Confirms shortest-path computation
Unreachable node Ensures -1 is returned correctly
Single node graph Tests minimum input size
Zero-weight edges Ensures zero weights are handled properly
Indirect path shorter than direct Confirms optimal path selection
Graph with cycle Ensures cycles do not break the algorithm
Intermediate shortest path Validates relaxation logic
Long chain graph Tests propagation through multiple nodes
Star graph Tests multiple neighbors from source

Edge Cases

One important edge case occurs when some nodes are unreachable from the starting node. A naive implementation might incorrectly return the maximum reachable distance without checking whether every node was visited. In this implementation, unreachable nodes retain a distance value of infinity. After the algorithm finishes, we explicitly check for infinity and return -1 if any node was never reached.

Another important edge case involves zero-weight edges. Some shortest-path implementations assume strictly positive weights, but this problem allows weights equal to zero. Dijkstra's algorithm still works correctly because the weights remain non-negative. The implementation properly handles zero-cost transitions during edge relaxation.

Graphs containing cycles are another common source of bugs. Without careful handling, an algorithm could repeatedly revisit nodes indefinitely. The priority queue approach avoids this issue because we only process improved distances. Outdated heap entries are skipped using:

if current_distance > distances[node]:
    continue

This ensures correctness and prevents unnecessary processing.

A final edge case is the smallest possible graph, where n = 1. In this situation, the starting node already has the signal, so the correct answer is 0. Since the distance array initializes distances[k] = 0, the implementation naturally handles this case correctly.