Introduction

Network Delay Time is one of the most popular applications of Dijkstra Algorithm.

You are given:

times[][]n
k

Where:

u → vtakes w time

Goal:

Find minimum time for signal from node k to reach all nodes.

If any node cannot be reached:

Return -1

Example

Input:

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

Output:

2

Key Observation

We need:

Shortest Distance from Source k to Every Node

This is exactly:

Dijkstra Algorithm

Algorithm

1. Build graph2. Start from node k
3. Run Dijkstra
4. Find maximum distance
5. Return answer

Dry Run

Source:

2

Distances:

1 = 1
2 = 0
3 = 1
4 = 2

Maximum:

2

Answer:

2

Approach : Dijkstra Algorithm

Explanation

  1. Start from source node.
  2. Use min heap.
  3. Always process smallest distance node.
  4. Relax neighbors.
  5. Track shortest distances.
  6. Return maximum shortest distance.

Practice

Complexity Analysis

Time Complexity: O((V + E) log V)Space Complexity: O(V + E)

Why This Problem is Important

  • Dijkstra Algorithm
  • Priority Queue
  • Shortest Path
  • Graph Traversal
  • Network Routing

Common Beginner Mistakes

  • Returning minimum distance instead of maximum
  • Forgetting unreachable nodes
  • Using BFS instead of Dijkstra
  • Not relaxing edges correctly
  • Wrong graph construction

Interview Tip

Always explain:

Run Dijkstra then returnmaximum shortest distance.

Related Questions

  • Dijkstra Algorithm
  • Cheapest Flights Within K Stops
  • Path With Minimum Effort
  • Swim In Rising Water

Final Takeaway

Network Delay Time is a classic Dijkstra problem.

It teaches:

  • Shortest Path Computation
  • Priority Queue Usage
  • Graph Traversal
  • Network Routing Concepts

Mastering Network Delay Time makes advanced shortest path problems significantly easier.