leetcode-743 Network Delay Time

# 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 n nodes to receive the signal. If it is impossible, return -1.
#
# Example 1:
# Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
# Output: 2
# Explanation: Signal sent from node 2 reaches:
# - Node 2 at time 0
# - Nodes 1 and 3 at time 1
# - Node 4 at time 2
# Maximum time is 2.
#
# Example 2:
# Input: times = [[1,2,1]], n = 2, k = 1
# Output: 1
#
# Example 3:
# Input: times = [[1,2,1]], n = 2, k = 2
# Output: -1
# Explanation: Node 1 cannot be reached from node 2.
#
# 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 (i.e., no multiple edges).

import heapq
from collections import defaultdict

class Solution:
    # Approach 1: Simple Relaxation (Most Intuitive - No Heap Needed)
    # Keep relaxing edges until no more updates possible
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # Initialize distances to infinity
        dist = [float('inf')] * (n + 1)
        dist[k] = 0  # Starting node has distance 0

        # Keep relaxing edges until no changes
        changed = True
        while changed:
            changed = False
            for u, v, w in times:
                # If we found a shorter path to v through u
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    changed = True

        # Get maximum distance (excluding index 0)
        max_dist = max(dist[1:])
        return max_dist if max_dist != float('inf') else -1


    # Approach 2: Dijkstra's Algorithm with Min-Heap (Optimal)
    def networkDelayTime2(self, times: List[List[int]], n: int, k: int) -> int:
        # Build adjacency list: node -> [(neighbor, weight)]
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        # Min-heap: (time, node)
        # Stores (distance_from_source, node)
        min_heap = [(0, k)]  # Start from node k at time 0

        # Track shortest time to reach each node
        dist = {}

        while min_heap:
            time, node = heapq.heappop(min_heap)

            # Skip if we've already found a shorter path to this node
            if node in dist:
                continue

            # Record the shortest time to reach this node
            dist[node] = time

            # Explore neighbors
            for neighbor, weight in graph[node]:
                if neighbor not in dist:
                    heapq.heappush(min_heap, (time + weight, neighbor))

        # Check if all nodes are reachable
        if len(dist) != n:
            return -1

        # Return maximum time (time for signal to reach all nodes)
        return max(dist.values())


    # Approach 3: Dijkstra with Distance Array
    def networkDelayTime3(self, times: List[List[int]], n: int, k: int) -> int:
        # Build graph
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        # Initialize distances to infinity
        dist = [float('inf')] * (n + 1)
        dist[k] = 0  # Distance to source is 0

        # Min-heap: (distance, node)
        min_heap = [(0, k)]

        while min_heap:
            d, node = heapq.heappop(min_heap)

            # Skip if we've found a better path already
            if d > dist[node]:
                continue

            # Relaxation: update distances to neighbors
            for neighbor, weight in graph[node]:
                new_dist = dist[node] + weight
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    heapq.heappush(min_heap, (new_dist, neighbor))

        # Get maximum distance (excluding index 0)
        max_dist = max(dist[1:])
        return max_dist if max_dist != float('inf') else -1


    # Approach 4: Bellman-Ford Algorithm (Fixed Iterations)
    def networkDelayTime4(self, times: List[List[int]], n: int, k: int) -> int:
        # Initialize distances
        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

        # Get maximum distance
        max_dist = max(dist[1:])
        return max_dist if max_dist != float('inf') else -1


    # Approach 5: DFS with Memoization (less efficient)
    def networkDelayTime5(self, times: List[List[int]], n: int, k: int) -> int:
        # Build graph
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        # Track minimum time to reach each node
        dist = {k: 0}

        def dfs(node, time):
            # If we've seen this node with shorter time, skip
            if node in dist and dist[node] <= time:
                return

            dist[node] = time

            for neighbor, weight in graph[node]:
                dfs(neighbor, time + weight)

        dfs(k, 0)

        if len(dist) != n:
            return -1

        return max(dist.values())

# Time & Space Complexity:
# Approach 1 (Simple Relaxation): Time O(V * E) worst case, Space O(V)
# Approach 2 (Dijkstra with Min-Heap): Time O((V + E) log V), Space O(V + E) - OPTIMAL
# Approach 3 (Dijkstra with Distance Array): Time O((V + E) log V), Space O(V + E)
# Approach 4 (Bellman-Ford): Time O(V * E), Space O(V)
# Approach 5 (DFS): Time O(V * E) or worse, Space O(V)
#
# Simple Relaxation Explanation (Approach 1):
# - Most intuitive approach, no heapq needed!
# - Keep trying to improve distances until no more improvements possible
# - For each edge (u->v with weight w), if dist[u] + w < dist[v], update dist[v]
# - Repeat until no changes occur in a full pass through all edges
# - Similar to Bellman-Ford but without fixed iteration count
# - Works because shortest paths can have at most (n-1) edges
# - Pro: Simple to understand and implement
# - Con: Can be slow (O(V*E)) compared to Dijkstra's O((V+E)logV)
#
# Dijkstra's Algorithm Explanation (Approach 2 & 3):
# 1. Start from source node with distance 0
# 2. Use min-heap to always process closest unvisited node
# 3. For each node, update distances to its neighbors (relaxation)
# 4. Continue until all reachable nodes are processed
# 5. Return maximum distance (or -1 if not all nodes reachable)
#
# Why Min-Heap?
# - Always process the node with shortest current distance
# - Guarantees we find shortest path to each node
# - Each node processed at most once (when popped from heap)
#
# Why Maximum Distance?
# - Signal propagates in parallel to all paths
# - All nodes receive signal simultaneously along shortest paths
# - Time for all nodes to receive = time for farthest node
#
# Visualization (Example 1):
# Graph: 2 -> 1 (weight 1)
#        2 -> 3 (weight 1)
#        3 -> 4 (weight 1)
#
# Starting from node 2:
# Time 0: Node 2 (distance 0)
# Time 1: Nodes 1, 3 (distance 1)
# Time 2: Node 4 (distance 1+1=2)
# Answer: max(0,1,1,2) = 2
#
# Key Differences from BFS:
# - BFS: Unweighted shortest path (all edges weight 1)
# - Dijkstra: Weighted shortest path (edges have different weights)
# - BFS uses queue, Dijkstra uses priority queue (min-heap)
#
# When to Use Dijkstra:
# ✓ Single-source shortest path
# ✓ Non-negative edge weights
# ✓ Directed or undirected graphs
# ✗ Negative edge weights (use Bellman-Ford instead)
#
# Related Problems:
# - Cheapest Flights Within K Stops (LC 787) - Modified Dijkstra
# - Path with Maximum Probability (LC 1514) - Max-heap variant
# - Minimum Cost to Make at Least One Valid Path (LC 1368)
# - Shortest Path in Binary Matrix (LC 1091) - Can use Dijkstra or BFS
#
# Common Pitfalls:
# 1. Forgetting to check if all nodes are reachable (return -1)
# 2. Using 0-indexed vs 1-indexed nodes
# 3. Not handling the case where heap contains outdated distances
# 4. Confusing min/max (need maximum distance here)