Network Delay Time

Asked byGoogleAmazon

Problem

Given a network of n nodes and a list of directed, weighted edges (travel times), along with a source node k, return the time for a signal starting at k to reach every node; return -1 if some node is unreachable.

Examples

Example 1

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

Output:2

Constraints

1 <= k <= n <= 100

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Advanced Graphs pattern

Beyond basic traversal, some graph problems need ordering constraints (topological sort) or weighted shortest paths (Dijkstra, Bellman-Ford, minimum spanning trees).

Look for this pattern when

The problem has ordering or prerequisite constraints ("do X before Y").
Edges have weights or costs and you need the cheapest path, not just any path.

Read the full Advanced Graphs guide →

Video walkthroughs

Original problem on LeetCode ↗