Network Delay Time
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: medium.
Topics: What is the Network Delay Time problem and how can it be solved efficiently in algorithms?, Graph, Directed Graph, Weighted Graph, Adjacency List, Shortest Path, Dijkstra's Algorithm, Priority Queue, Heap/Priority Queue, Time Complexity, Space Complexity, graph representation, complexity analysis, priority queue, dijkstra's algorithm, shortest path algorithms, bfs.
Problem Name: Network Delay Time 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 ui to vi. 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 for all n nodes to receive the signal, return 1. Input Specification: n: an integer, the number of nodes. times: a list of lists/tuples, where each inner list/tuple [ui, vi, wi] represents a directed edge from node ui to node vi with travel time wi. k: an integer, the source node from which the signal is sent. Output Specification: An integer representing the minimum time it takes for all n nodes to receive the signal, or 1 if not all nodes can be reached. Constraints: 1 <= n <= 100 0 <= times.length <= 6000 times[i].length == 3 1 <= ui, vi <= n ui != vi 0 <= wi <= 100 1 <= k <= n All the pairs (ui, vi) are unique. Sample Test Cases: Sample 1: Input: times = [[2,1,1],[2,3,1],[3,4,1]] n = 4 k = 2 Output: 2 Explanation: The signal starts at node 2. Node 2 to Node 1: time 1 Node 2 to Node 3: time 1 Node 3 to Node 4: time 1 Shortest times from node 2: To node 1: 1 To node 2: 0 To node 3: 1 To node 4: 2 (2 3 4) The maximum of these shortest times is 2. Sample 2: Input: times = [[1,2,1]] n = 2 k = 1 Output: 1 Sample 3: Input: times = [[1,2,1]] n = 2 k = 2 Output: 1 Explanation: Node 1 cannot be reached from node 2.