What is the time and space complexity of Network Delay Time?

Time complexity: O(V² + E). Space complexity: O(V + E).

Network Delay Time

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Network Delay Time

Approach

Run Dijkstra-like relaxation with visited set and smallest-unreached node in O(V²). Initialize source distance to 0 and repeatedly relax outgoing edges.

Complexity Analysis

Time: O(V² + E)
Space: O(V + E)

Pattern

Shortest Path (Dijkstra without Heap)

Why It Works

Each step finalizes the node with smallest tentative distance, then relaxes edges. This guarantees shortest distances in non-negative weighted graphs.

Updated Mar 2026