743. Network Delay Time

This problem asks to find the minimum time it takes for a signal to reach all nodes in a network starting from a given node k. The network is represented as a directed graph where edges have weights representing travel times.

Approach

This problem can be efficiently solved using Dijkstra's algorithm, which finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. Two variations are presented: a naive implementation and an optimized version using a min-heap (priority queue).

Solution 1: Naive Dijkstra Algorithm

This solution directly implements Dijkstra's algorithm. It iteratively selects the unvisited node with the minimum distance from the source and updates the distances to its neighbors.

Time Complexity: O(n² + m), where n is the number of nodes and m is the number of edges. The nested loops in the main part of the algorithm contribute to the O(n²) complexity.

Space Complexity: O(n²), due to the adjacency matrix g.

Solution 2: Heap-Optimized Dijkstra Algorithm

This solution improves upon the naive approach by using a min-heap (priority queue) to efficiently select the node with the minimum distance. The heap ensures that the node with the smallest distance is always at the top, reducing the time complexity.

Time Complexity: O(m log m + n). The m log m term comes from the heap operations (insertion and extraction), and the n term accounts for iterating through nodes. This is generally faster than the naive approach for sparse graphs (where m is significantly smaller than n²).

Space Complexity: O(n + m). The space used by the heap and adjacency list is proportional to the number of nodes and edges.

Code Implementations

The code for both solutions is provided in multiple languages. The key differences lie in how the graph is represented and how the priority queue is implemented.

Note: The code includes error handling to return -1 if it's impossible to reach all nodes. This happens when the maximum distance remains infinity after the algorithm completes. The inf variable represents a large value indicating infinity.

(Python3, Solution 1)

import sys
 
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[sys.maxsize] * n for _ in range(n)]  # Adjacency matrix
        for u, v, w in times:
            g[u - 1][v - 1] = w
        dist = [sys.maxsize] * n
        dist[k - 1] = 0
        vis = [False] * n
        for _ in range(n):
            t = -1
            for j in range(n):
                if not vis[j] and (t == -1 or dist[t] > dist[j]):
                    t = j
            vis[t] = True
            for j in range(n):
                dist[j] = min(dist[j], dist[t] + g[t][j])
        ans = max(dist)
        return -1 if ans == sys.maxsize else ans
 

(Python3, Solution 2)

import heapq
 
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]  # Adjacency list
        for u, v, w in times:
            g[u - 1].append((v - 1, w))
        dist = [float('inf')] * n
        dist[k - 1] = 0
        pq = [(0, k - 1)]  # (distance, node)
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in g[u]:
                if dist[v] > dist[u] + w:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))
        ans = max(dist)
        return -1 if ans == float('inf') else ans
 

Similar implementations are available in Java, C++, Go, and TypeScript, reflecting the core algorithm and data structure choices described above. The specific syntax and libraries used may differ, but the underlying logic remains consistent with Dijkstra's algorithm.