# 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 the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Example 1
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 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
# Solution
Approach 1: Dijkstra's.
# Code (Python)
Approach 1:
import heapq
class Solution:
def networkDelayTime(self, times, n: int, k: int) -> int:
# Dijkstra: find shortest paths for graphs with positive edges from 1 source vertex to all others
# Explanation -- https://leetcode.com/discuss/general-discussion/1059477/A-noob's-guide-to-Djikstra's-Algorithm
k = k - 1 # translate to 0 indexed
edges = {i: [] for i in range(n)}
for start, end, length in times:
edges[start - 1].append((end - 1, length))
known_distances = [float('inf') for _ in range(n)] # necessary only to get all distances; otherwise not necessary
visited = set()
explore_list = [(0, k)]
heapq.heapify(explore_list)
while explore_list:
distance, vertex = heapq.heappop(explore_list)
if vertex in visited:
continue
visited.add(vertex)
known_distances[vertex] = distance
for neighbor, length in edges[vertex]:
if neighbor not in visited:
heapq.heappush(explore_list, (distance + length, neighbor))
return -1 if max(known_distances) == float('inf') else max(known_distances)
# Code (C++)
Approach 1:
Approach 2: