Pseudo-code for Naive Approach

text
function dfs(node, currentTime):
    if currentTime >= recordedTime[node]:
        return
    recordedTime[node] = currentTime
    
    for neighbor, weight in graph[node]:
        dfs(neighbor, currentTime + weight)

Why this approach fails

1. Inefficiency: This approach essentially performs a relaxation step similar to the Bellman-Ford algorithm but without the structural optimization. In a dense graph or a graph with cycles (even if weights are positive), the recursion might re-visit nodes exponentially many times as it finds incrementally better paths.
2. Time Complexity: In the worst case, the time complexity can approach $O(N!)$ or $O(N^N)$ depending on the graph structure, leading to a Time Limit Exceeded (TLE) error on LeetCode.
3. Lack of Greediness: Standard DFS does not prioritize shorter paths. It might explore a path with weight 100 before exploring a path with weight 1, requiring extensive backtracking and updates.

Core Insight for Network Delay Time

The intuition for moving from a brute force approach to Dijkstra's Algorithm lies in the greedy nature of signal propagation. A signal always arrives at a node via the fastest available route.

If we are standing at the source node k, the very first node the signal will reach is the immediate neighbor connected by the edge with the smallest weight. Once the signal reaches that neighbor, we can consider that node "visited" or "finalized" because no other path could possibly reach it faster (assuming non-negative weights).

Key Invariant: Dijkstra's algorithm maintains a priority queue of nodes to visit, ordered by their current known distance from the source. The invariant is that when we extract a node from the priority queue, the distance associated with it is the globally optimal shortest path to that node.

Visual Description: Imagine the algorithm as a wavefront expanding from node k.

1. Initially, only k is reachable (time 0).
2. The algorithm looks at all boundaries of the current wavefront (edges leading out of reached nodes).
3. It picks the boundary node that adds the least total time to the path.
4. This node is absorbed into the "finalized" set.
5. This process repeats. The priority queue acts as the manager of this wavefront, ensuring we always expand the path that has the minimum total accumulated weight.

Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)

To implement the optimal solution for LeetCode 743, we strictly follow the Dijkstra subpattern:

1. Graph Representation: Convert the input times list into an adjacency list where graph[u] contains pairs of (v, w).
2. Distance Tracking: Maintain an array dist (or a hash map) initialized to infinity (∞) for all nodes, except the source node k, which is initialized to 0. This array tracks the shortest time found so far to reach each node.
3. Priority Queue: Use a Min-Heap to store pairs of (time, node). Initialize it with (0, k). The heap ensures we always process the node with the smallest accumulated time next.
4. Traversal & Relaxation:
   • While the heap is not empty, pop the element with the smallest time: (curr_time, u).
   • Crucial Check: If curr_time is greater than dist[u], it means we found a shorter path to u previously, and this is a "stale" entry. Discard it.
   • Iterate through neighbors v of u with weight w.
   • If curr_time + w < dist[v], we have found a faster way to reach v. Update dist[v] = curr_time + w and push (dist[v], v) into the heap.
5. Result Calculation: After the heap is empty, inspect the dist array.
   • If any node still has a distance of infinity, it means it is unreachable. Return -1.
   • Otherwise, the answer is the maximum value in the dist array (ignoring the 0th index if using 1-based indexing).

Execution Flow

Let's trace the algorithm with Example 1: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2.

1. Initialization:

   • Adjacency List: {2: [(1, 1), (3, 1)], 3: [(4, 1)]}
   • dist array: [INF, INF, 0, INF, INF] (Indices 0 to 4, 0 is unused)
   • Min-Heap: [(0, 2)] (Format: time, node)

2. Iteration 1:

   • Pop (0, 2). Node 2 is finalized.
   • Neighbors of 2:
     • Node 1 (weight 1): 0 + 1 < INF. Update dist[1] = 1. Push (1, 1).
     • Node 3 (weight 1): 0 + 1 < INF. Update dist[3] = 1. Push (1, 3).
   • Heap: [(1, 1), (1, 3)]

3. Iteration 2:

   • Pop (1, 1). Node 1 is finalized.
   • Neighbors of 1: None.
   • Heap: [(1, 3)]

4. Iteration 3:

   • Pop (1, 3). Node 3 is finalized.
   • Neighbors of 3:
     • Node 4 (weight 1): 1 + 1 < INF. Update dist[4] = 2. Push (2, 4).
   • Heap: [(2, 4)]

5. Iteration 4:

   • Pop (2, 4). Node 4 is finalized.
   • Neighbors of 4: None.
   • Heap: [] (Empty)

6. Final Calculation:

   • dist array: [INF, 1, 0, 1, 2]
   • Max value (indices 1-4): 2.
   • Return 2.

Proof of Correctness

Dijkstra's algorithm is proven correct for graphs with non-negative edge weights. The correctness relies on the greedy choice property. When we extract a node u with distance d from the priority queue, we assert that there is no other path to u shorter than d.

Suppose there existed a path shorter than d. This path would have to pass through some other node v currently in the priority queue (or the frontier). However, since u was picked before v, the distance to v must be greater than or equal to d (since the queue is a Min-Heap). Because edge weights are non-negative, extending the path from v can only increase the total distance. Thus, no path through v can result in a shorter distance to u.

This guarantees that dist contains the true shortest path for all reachable nodes.

Reference Implementation

C++ Solution for LeetCode 743

cpp
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // Adjacency list: node -> vector of {neighbor, weight}
        vector<vector<pair<int, int>>> adj(n + 1);
        for (const auto& t : times) {
            adj[t[0]].push_back({t[1], t[2]});
        }

        // Min-heap priority queue: {time, node}
        // Orders by time ascending
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        // Distance array initialized to infinity
        const int INF = 1e9;
        vector<int> dist(n + 1, INF);

        // Start from node k
        dist[k] = 0;
        pq.push({0, k});

        while (!pq.empty()) {
            int currTime = pq.top().first;
            int u = pq.top().second;
            pq.pop();

            // If we found a shorter path to u already, skip this stale entry
            if (currTime > dist[u]) {
                continue;
            }

            for (auto& edge : adj[u]) {
                int v = edge.first;
                int weight = edge.second;

                // Relaxation step
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }

        // Find the maximum time needed
        int maxTime = 0;
        for (int i = 1; i <= n; ++i) {
            if (dist[i] == INF) return -1; // Unreachable node
            maxTime = max(maxTime, dist[i]);
        }

        return maxTime;
    }
};

Java Solution for LeetCode 743

java
import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Adjacency list
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] time : times) {
            graph.putIfAbsent(time[0], new ArrayList<>());
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        // Min-heap storing {time, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        // Distance array
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        dist[k] = 0;
        pq.offer(new int[]{0, k});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currTime = curr[0];
            int u = curr[1];

            // Skip stale entries
            if (currTime > dist[u]) {
                continue;
            }

            if (graph.containsKey(u)) {
                for (int[] edge : graph.get(u)) {
                    int v = edge[0];
                    int weight = edge[1];

                    if (dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        pq.offer(new int[]{dist[v], v});
                    }
                }
            }
        }

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            maxTime = Math.max(maxTime, dist[i]);
        }

        return maxTime;
    }
}

Python Solution for LeetCode 743

python
import heapq
from collections import defaultdict

class Solution:
    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))
            
        # Min-heap stores (time, node)
        pq = [(0, k)]
        
        # Track minimum time to reach each node
        # Initialize with infinity
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0
        
        while pq:
            curr_time, u = heapq.heappop(pq)
            
            # Optimization: If we pulled a stale path, ignore it
            if curr_time > dist[u]:
                continue
            
            for v, weight in graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    heapq.heappush(pq, (dist[v], v))
                    
        # Find the max time among all shortest paths
        max_time = max(dist.values())
        
        return max_time if max_time != float('inf') else -1