Network Delay Time - Leetcode Solution

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] = (u, v, w), where u is the source node, v is the target node, and w 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 time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Solution:

We are given a weighted directed graph where the weight represents the time taken to reach the destination node from the source node and we want to find the shortest path from a starting node to all other nodes in the graph. We can use Dijkstra's algorithm to solve this problem.

Firstly, we create an adjacency list of the given graph. Then, we initialize the distance of the starting node to be zero and all the other nodes as infinity. We create a min-heap to maintain the minimum distance from the starting node to any node. We push the starting node into the min-heap with distance as 0.

While the min-heap is not empty, we extract the node with the minimum distance value from the min-heap, say u. We iterate through all its neighbours v, and for each neighbour, we calculate its distance through u, let's call it dist. If the distance obtained is less than the current distance of v, then we update the distance of v and push the updated distance and v into the min-heap.

Finally, we return the maximum distance obtained from the starting node to all other nodes. If any node's distance value remains infinity, it means that it is not reachable from the starting node and hence we return -1.

Here is the Python solution:

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # Create adjacency list to represent the graph
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        # Initialize distance of all nodes from source
        dist = [float('inf')] * (n+1)
        dist[k] = 0
        
        # Create a min-heap to maintain minimum distance
        min_heap = [(0, k)]
        visited = set()
        
        while min_heap:
            d, u = heapq.heappop(min_heap)
            if u in visited:
                continue
            visited.add(u)
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(min_heap, (dist[v], v))
        
        max_dist = max(dist[1:])
        return max_dist if max_dist < float('inf') else -1

Time Complexity: The time complexity of Dijkstra's algorithm is O(E + V log V), where E is the number of edges and V is the number of vertices, since we are using a min-heap to maintain minimum distance.

Space Complexity: The space complexity is O(V + E) for the adjacency list and min-heap.

In conclusion, we can use Dijkstra's algorithm to solve the network delay time problem on Leetcode. It is a standard graph algorithm to find the shortest path from a starting node to all other nodes in a weighted directed graph.

1