Abstract / Summary

Given a network with travel times between nodes find the minimum time for a signal to reach all nodes starting from a given source.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 54% (900k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph
• Heap (Priority Queue)
• Shortest Path

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “network delay time” problem: given a directed weighted graph described by times, the number of nodes n, and a source node k, it computes the earliest moment when all nodes receive a signal sent from k. If any node cannot be reached, the function returns -1. The algorithm builds an adjacency map, then iteratively relaxes edge distances using a frontier set, finally extracting the maximum arrival time among reachable nodes.

Key Steps

Building the adjacency structure

edges = defaultdict(dict)
for t in times:
    edges[t[0]][t[1]] = t[2]

A defaultdict of dictionaries stores outgoing edges for each source node. Each entry edges[u][v] holds the travel time from u to v. If multiple entries for the same directed edge appear, the later one overwrites the previous, ensuring the most recent weight is used.

Initializing distance tracking

have = { k : 0 }
todo = set([ k ])

have maps each node to the shortest known arrival time from the source. The source k starts with a distance of 0. todo holds the current frontier of nodes whose outgoing edges need to be examined.

Frontier-driven relaxation loop

while todo:
    next = set()
    for t in todo:
        for e in edges[t]:
            duration = have[t] + edges[t][e]
            if e not in have or have[e] > duration:
                have[e] = duration
                next.add(e)
    todo = next

The loop processes all nodes in todo. For each outgoing edge (t, e), it computes a candidate arrival time duration. If e has not been visited or a shorter path is found, have[e] is updated and e is added to next. After scanning the current frontier, todo is replaced by next, driving the algorithm forward until no new improvements are possible.

Determining reachability and final result

if len(have) != n:
    return -1
return max(have.values())

If the number of nodes recorded in have is less than n, at least one node is unreachable, and -1 is returned. Otherwise, the maximum value in have represents the time when the last node receives the signal.

Edge Cases Handled

The code gracefully handles a graph with a single node (n == 1). In that scenario have contains only the source node, the length check passes, and max(have.values()) yields 0, correctly indicating no delay.

When times is empty but n > 1, the adjacency map remains empty, the frontier processes only the source node, and the length check fails, causing a return of -1. This captures the situation where no edges exist to reach other nodes.

Duplicate edges between the same ordered pair of nodes are resolved by the assignment edges[t[0]][t[1]] = t[2]. The later entry overwrites the earlier one, ensuring a deterministic weight is used for relaxation.

Self-loops (edges where source equals destination) are stored but never affect the result because the algorithm only updates a node’s distance if a strictly shorter path is found; the self-loop would produce a non-negative addition to an already optimal distance, leaving have unchanged.

Disconnected subgraphs are detected by the final size comparison. Any node that never appears in have is unreachable, leading to the prescribed -1 outcome.

Performance Optimizations

The adjacency map uses a defaultdict(dict), providing O(1) average-time access to outgoing edges without the overhead of constructing a full adjacency matrix.

The frontier set todo eliminates duplicate processing of the same node within a single iteration, because a node is added to next only when a strictly better distance is discovered. This reduces unnecessary edge scans compared to a naïve repeated full-graph traversal.

By storing distances in the have dictionary, the algorithm avoids revisiting nodes whose shortest distance is already known, akin to the visited set in Dijkstra’s algorithm but without a priority queue. This yields a lightweight relaxation step that runs efficiently for sparse graphs.

The loop terminates as soon as no further improvements are possible, which can happen well before all edges are examined in dense graphs, saving work when the reachable portion of the network is limited.

Overall, the combination of a compact adjacency representation, set-based frontier management, and early termination contributes to a fast execution profile for typical inputs.

Imagine a magical map with many secret caves all connected by tunnels. Some tunnels are very short while others take a long time to walk through. A message starts at one special cave and needs to travel to every single cave on the map to deliver the news.

Think of the code as a helpful robot that wants to find out how quickly this message can reach everyone. The robot keeps a notebook to write down the fastest way to get the message to each cave.

At the start, the robot puts the message in the special cave and notes that it takes zero time to be there. Then, the robot looks at all the tunnels leading out from that cave. It calculates how long the message takes to reach the next cave and writes that number in the notebook.

If the robot finds a cave that has not heard the news yet, or if it finds a new path that is faster than the one it already wrote down, it updates the notebook. Then it moves to the next set of connected caves to keep delivering the message. This continue until there are no more tunnels to follow. Finally, the robot looks at all the numbers in the notebook to see which cave took the longest time to receive the message. If some caves were never reached because there were no tunnels to get there, the robot knows the mission was not finished.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java					Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis					JS
	fpdjsns	C++
	fsq		Python
	JoshCrozier					JS
	lkwq007		Python
	MacJim	C++
	martianoff						Scala
	qiyuangong			Java
	ruoru							Rust
	shreymehul				C#
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	Python
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
martianoff	Scala
qiyuangong	Java
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality