Network Delay Time (Dijkstra's Algorithm)

Find the time it takes for a signal to reach all nodes in a network using shortest path algorithms

Language Selection

Choose your preferred programming language

Showing: Python

Network Delay Time (Dijkstra’s Algorithm)

Problem Statement

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.

Input/Output Specifications

Input:
- times: Array of directed edges with travel times [source, target, time]
- n: Number of nodes in the network (labeled 1 to n)
- k: Source node from which signal is sent
Output: Minimum time for signal to reach all nodes, or -1 if impossible
Constraints:
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- All pairs (ui, vi) are unique

Examples

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: 
Signal starts at node 2
- Node 1 receives signal at time 1
- Node 3 receives signal at time 1  
- Node 4 receives signal at time 2 (via 3)
All nodes receive signal by time 2.

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation:
Signal goes from node 1 to node 2 in time 1.

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation:
Signal starts at node 2, but node 1 is unreachable.

Example 4:

Input: times = [], n = 1, k = 1
Output: 0
Explanation:
Only one node exists and signal starts there.

Solution Approaches

Approach 1: Dijkstra’s Algorithm with Priority Queue (Optimal)

Use Dijkstra’s algorithm to find shortest paths from source to all nodes in a weighted directed graph.

Algorithm Explanation

Initialize: Create adjacency list and distance array with infinity values
Priority Queue: Use min-heap to always process the closest unvisited node
Relaxation: For each node, update distances to its neighbors if shorter path found
Termination: Continue until all reachable nodes are processed
Result: Return maximum distance if all nodes reachable, otherwise -1

Implementation

Python:

import heapq
from collections import defaultdict

class Solution:
    """
    Dijkstra's algorithm for shortest path in weighted graph
    Time: O((V + E) log V) where V is nodes, E is edges
    Space: O(V + E) for adjacency list and priority queue
    """
    
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        # Build adjacency list
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        # Initialize distances with infinity
        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        
        # Priority queue: (distance, node)
        pq = [(0, k)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            # Skip if we've already found a shorter path
            if d > dist[u]:
                continue
            
            # Relax all neighbors
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))
        
        # Find maximum distance (excluding index 0)
        max_dist = max(dist[1:])
        return max_dist if max_dist != float('inf') else -1

Java:

class Solution {
    /**
     * Dijkstra's algorithm for shortest path in weighted graph
     * Time: O((V + E) log V) where V is nodes, E is edges
     * Space: O(V + E) for adjacency list and priority queue
     */
    
    public int networkDelayTime(int[][] times, int n, int k) {
        // Build adjacency list
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] time : times) {
            graph.computeIfAbsent(time[0], x -> new ArrayList<>())
                 .add(new int[]{time[1], time[2]});
        }
        
        // Initialize distances with infinity
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        
        // Priority queue: (distance, node)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            
            // Skip if we've already found a shorter path
            if (d > dist[u]) continue;
            
            // Relax all neighbors
            if (graph.containsKey(u)) {
                for (int[] edge : graph.get(u)) {
                    int v = edge[0], w = edge[1];
                    if (dist[u] + w < dist[v]) {
                        dist[v] = dist[u] + w;
                        pq.offer(new int[]{dist[v], v});
                    }
                }
            }
        }
        
        // Find maximum distance (excluding index 0)
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxDist = Math.max(maxDist, dist[i]);
        }
        
        return maxDist;
    }
}

Go:

import (
    "container/heap"
    "math"
)

// PriorityQueue implements heap.Interface for dijkstra
type PriorityQueue [][2]int

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i][0] < pq[j][0] }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.([2]int))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

// networkDelayTime - Dijkstra's algorithm for shortest path
// Time: O((V + E) log V) where V is nodes, E is edges
// Space: O(V + E) for adjacency list and priority queue
func networkDelayTime(times [][]int, n int, k int) int {
    // Build adjacency list
    graph := make(map[int][][2]int)
    for _, time := range times {
        u, v, w := time[0], time[1], time[2]
        graph[u] = append(graph[u], [2]int{v, w})
    }
    
    // Initialize distances with infinity
    dist := make([]int, n+1)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[k] = 0
    
    // Priority queue: [distance, node]
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, [2]int{0, k})
    
    for pq.Len() > 0 {
        curr := heap.Pop(pq).([2]int)
        d, u := curr[0], curr[1]
        
        // Skip if we've already found a shorter path
        if d > dist[u] {
            continue
        }
        
        // Relax all neighbors
        for _, edge := range graph[u] {
            v, w := edge[0], edge[1]
            if dist[u]+w < dist[v] {
                dist[v] = dist[u] + w
                heap.Push(pq, [2]int{dist[v], v})
            }
        }
    }
    
    // Find maximum distance (excluding index 0)
    maxDist := 0
    for i := 1; i <= n; i++ {
        if dist[i] == math.MaxInt32 {
            return -1
        }
        if dist[i] > maxDist {
            maxDist = dist[i]
        }
    }
    
    return maxDist
}

JavaScript:

/**
 * Dijkstra's algorithm for shortest path in weighted graph
 * Time: O((V + E) log V) where V is nodes, E is edges
 * Space: O(V + E) for adjacency list and priority queue
 */
function networkDelayTime(times, n, k) {
    // Build adjacency list
    const graph = new Map();
    for (const [u, v, w] of times) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push([v, w]);
    }
    
    // Initialize distances with infinity
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    
    // Priority queue simulation with array (for simplicity)
    const pq = [[0, k]]; // [distance, node]
    
    while (pq.length > 0) {
        // Find minimum distance node (inefficient but simple)
        let minIdx = 0;
        for (let i = 1; i < pq.length; i++) {
            if (pq[i][0] < pq[minIdx][0]) {
                minIdx = i;
            }
        }
        
        const [d, u] = pq.splice(minIdx, 1)[0];
        
        // Skip if we've already found a shorter path
        if (d > dist[u]) continue;
        
        // Relax all neighbors
        if (graph.has(u)) {
            for (const [v, w] of graph.get(u)) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push([dist[v], v]);
                }
            }
        }
    }
    
    // Find maximum distance (excluding index 0)
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }
    
    return maxDist;
}

C#:

public class Solution {
    /// <summary>
    /// Dijkstra's algorithm for shortest path in weighted graph
    /// Time: O((V + E) log V) where V is nodes, E is edges
    /// Space: O(V + E) for adjacency list and priority queue
    /// </summary>
    
    public int NetworkDelayTime(int[][] times, int n, int k) {
        // Build adjacency list
        var graph = new Dictionary<int, List<(int, int)>>();
        foreach (var time in times) {
            if (!graph.ContainsKey(time[0])) {
                graph[time[0]] = new List<(int, int)>();
            }
            graph[time[0]].Add((time[1], time[2]));
        }
        
        // Initialize distances with infinity
        var dist = new int[n + 1];
        Array.Fill(dist, int.MaxValue);
        dist[k] = 0;
        
        // Priority queue: (distance, node)
        var pq = new SortedSet<(int dist, int node)>();
        pq.Add((0, k));
        
        while (pq.Count > 0) {
            var (d, u) = pq.Min;
            pq.Remove(pq.Min);
            
            // Skip if we've already found a shorter path
            if (d > dist[u]) continue;
            
            // Relax all neighbors
            if (graph.ContainsKey(u)) {
                foreach (var (v, w) in graph[u]) {
                    if (dist[u] + w < dist[v]) {
                        pq.Remove((dist[v], v)); // Remove old entry
                        dist[v] = dist[u] + w;
                        pq.Add((dist[v], v));
                    }
                }
            }
        }
        
        // Find maximum distance (excluding index 0)
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == int.MaxValue) return -1;
            maxDist = Math.Max(maxDist, dist[i]);
        }
        
        return maxDist;
    }
}

Approach 2: Bellman-Ford Algorithm

Use Bellman-Ford algorithm that can handle negative weights and detect negative cycles.

Algorithm Explanation

Initialize: Set distance to source as 0, all others as infinity
Relaxation: Repeat (V-1) times: for each edge, relax if shorter path found
Negative Cycle Detection: Check if any edge can still be relaxed
Result: Return maximum distance if no negative cycles

Implementation

Python:

class Solution:
    """
    Bellman-Ford algorithm for shortest path (handles negative weights)
    Time: O(VE) where V is nodes, E is edges
    Space: O(V) for distance array
    """
    
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        # Initialize distances with infinity
        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        
        # Relax edges (n-1) times
        for _ in range(n - 1):
            for u, v, w in times:
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
        
        # Check for negative cycles (not applicable here since weights >= 0)
        for u, v, w in times:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                return -1  # Negative cycle detected
        
        # Find maximum distance (excluding index 0)
        max_dist = max(dist[1:])
        return max_dist if max_dist != float('inf') else -1

Approach 3: Floyd-Warshall Algorithm

Use Floyd-Warshall for all-pairs shortest paths (overkill for this problem but educational).

Python:

class Solution:
    """
    Floyd-Warshall algorithm for all-pairs shortest paths
    Time: O(V^3) where V is nodes
    Space: O(V^2) for distance matrix
    """
    
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        # Initialize distance matrix
        dist = [[float('inf')] * (n + 1) for _ in range(n + 1)]
        
        # Distance from node to itself is 0
        for i in range(1, n + 1):
            dist[i][i] = 0
        
        # Fill direct edges
        for u, v, w in times:
            dist[u][v] = w
        
        # Floyd-Warshall: try all intermediate nodes
        for k_node in range(1, n + 1):
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    if dist[i][k_node] + dist[k_node][j] < dist[i][j]:
                        dist[i][j] = dist[i][k_node] + dist[k_node][j]
        
        # Find maximum distance from source k
        max_dist = 0
        for i in range(1, n + 1):
            if dist[k][i] == float('inf'):
                return -1
            max_dist = max(max_dist, dist[k][i])
        
        return max_dist

Complexity Analysis

Dijkstra’s Algorithm

Time Complexity: O((V + E) log V) using binary heap
Space Complexity: O(V + E) for adjacency list and priority queue

Bellman-Ford Algorithm

Time Complexity: O(VE) where V is vertices and E is edges
Space Complexity: O(V) for distance array

Floyd-Warshall Algorithm

Time Complexity: O(V³) for all-pairs shortest paths
Space Complexity: O(V²) for distance matrix

Key Insights

Single-Source Shortest Path: This is a classic SSSP problem ideal for Dijkstra’s algorithm
Non-negative Weights: All edge weights are non-negative, making Dijkstra optimal
Maximum of Minimums: Need maximum of all shortest distances to ensure all nodes receive signal
Reachability: If any node is unreachable, return -1

Edge Cases

Single Node: Only source node exists (n=1, k=1) → return 0
No Edges: No outgoing edges from source → check if n=1
Unreachable Nodes: Some nodes cannot be reached from source → return -1
Self-Loop: Source has self-loop (doesn’t affect result)
Multiple Paths: Multiple paths to same node (algorithm finds shortest)
Disconnected Graph: Source cannot reach all nodes

Test Cases

# Test cases for validation
def test_network_delay():
    solution = Solution()
    
    # Test case 1: Basic example
    assert solution.networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2) == 2
    
    # Test case 2: Simple path
    assert solution.networkDelayTime([[1,2,1]], 2, 1) == 1
    
    # Test case 3: Unreachable node
    assert solution.networkDelayTime([[1,2,1]], 2, 2) == -1
    
    # Test case 4: Single node
    assert solution.networkDelayTime([], 1, 1) == 0
    
    # Test case 5: Multiple paths
    assert solution.networkDelayTime([[1,2,1],[1,3,4],[2,3,2]], 3, 1) == 3
    
    # Test case 6: All connected
    assert solution.networkDelayTime([[1,2,1],[2,3,2],[1,3,4]], 3, 1) == 3

Follow-up Questions

Path Reconstruction: Return the actual shortest paths, not just distances
Dynamic Updates: Handle edge weight updates efficiently
Multiple Sources: Signal sent from multiple sources simultaneously
Bandwidth Constraints: Consider edge capacity limitations

Common Mistakes

Index Confusion: Nodes are 1-indexed, but arrays might be 0-indexed
Infinity Handling: Not properly checking for unreachable nodes
Priority Queue: Using max-heap instead of min-heap
Early Termination: Not processing all nodes when finding maximum

Interview Tips

Recognize Pattern: Identify this as single-source shortest path problem
Choose Algorithm: Dijkstra is optimal for non-negative weights
Explain Trade-offs: Compare Dijkstra vs Bellman-Ford vs Floyd-Warshall
Handle Edge Cases: Consider single node and unreachable scenarios
Optimize Implementation: Discuss using Fibonacci heap for better complexity
Code Incrementally: Start with graph building, then implement Dijkstra

Algorithm Comparison

Algorithm	Time Complexity	Space Complexity	Use Case
Dijkstra	O((V+E)logV)	O(V+E)	Non-negative weights, SSSP
Bellman-Ford	O(VE)	O(V)	Negative weights, cycle detection
Floyd-Warshall	O(V³)	O(V²)	All-pairs shortest paths

Real-World Applications

Network Routing: Internet packet routing protocols
GPS Navigation: Finding shortest travel time routes
Social Networks: Message propagation analysis
Supply Chain: Distribution time optimization