MediumGraphs · Shortest Path · Heap

Network Delay Time

Nodes 1…n are joined by directed edges times[i] = [u, v, t] (signal takes t to go from u to v). A signal starts at node k. Return how long until every node has it, or -1 if some node never does.

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

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

The network

The number under each node is when the signal reaches it

Time and space complexity

V = n nodes, E = len(times). The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. Up to 7 nodes and 14 edges, times from 0 to 99, each (u, v) pair at most once.