Understanding Network Delay Time
Return the time for a signal from source to reach every vertex in a directed weighted graph, or -1 if any vertex is unreachable.
How it works
With nonnegative weights, the unfinished vertex with the smallest tentative distance can be finalized safely.
Initialize source to zero and other distances to an unreachable sentinel. Choose the unsettled vertex with the smallest distance. Finalize it and relax outgoing edges, then take the maximum final distance.
Try an example
Input: n = 4, edges = [[0, 1, 5], [0, 2, 1], [2, 1, 1], [1, 3, 2]], source = 0
Output: 4
With nonnegative weights, the unfinished vertex with the smallest tentative distance can be finalized safely.
Constraints
- 1–16 vertices numbered 0 through n - 1; at most 48 edges [from, to, weight].
- Weights are integers from 0 through 1,000. Repeated edges and self-loops are allowed.
- Source and all edge endpoints must be valid vertices.
Use the simulator
Change the input, then choose Visualize input. Use Next and Previous to inspect each decision, or Play to advance automatically. Compare approaches and their complexity. Choose Try yourself to write JavaScript, select My code and Visualize code to inspect its execution, or Run Tests to check results.
Execution happens in your browser. Drafts are saved locally; avoid entering secrets or sensitive information.