network_delay_time
1from collections import defaultdict 2from heapq import heappush, heappop 3 4 5# @leet start 6class Solution: 7 def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int: 8 """ 9 This question asks us to find the shortest path to all nodes starting 10 from a given node, `k`. 11 If we cannot reach all nodes, the count of which is `n`, return -1. 12 13 This is a classic use for Dijkstra's algorithm. We first turn the graph 14 into a key value mapping of source -> (cost, target). 15 16 We do this because we want to create a min heap, required for dijkstra's. 17 We then create a heap, which starts out with our starting node, `k`. 18 19 Next, we pop from the heap and check if we've visited the node already. 20 If so, we continue, otherwise, we know we have the minimum cost 21 to get to the node. Then, for all of its neighbors, we add it to the heap 22 with its cost + our current cost. 23 24 Finally, after traversing through all the nodes we can, if we can't 25 reach all nodes, return -1, otherwise the maximum delay time is the 26 maximum time we've encountered so far. 27 """ 28 graph = defaultdict(list) 29 30 for source, target, cost in times: 31 graph[source].append((cost, target)) 32 33 heap = [(0, k)] 34 costs = {} 35 36 while heap: 37 cost, node = heappop(heap) 38 39 if node in costs: 40 continue 41 42 costs[node] = cost 43 for neighbor_cost, neighbor in graph[node]: 44 heappush(heap, (cost + neighbor_cost, neighbor)) 45 46 if len(costs) != n: 47 return -1 48 49 return max(costs.values()) 50 51 52# @leet end 53 54 55def test(): 56 assert 2 + 2 == 4
class
Solution:
7class Solution: 8 def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int: 9 """ 10 This question asks us to find the shortest path to all nodes starting 11 from a given node, `k`. 12 If we cannot reach all nodes, the count of which is `n`, return -1. 13 14 This is a classic use for Dijkstra's algorithm. We first turn the graph 15 into a key value mapping of source -> (cost, target). 16 17 We do this because we want to create a min heap, required for dijkstra's. 18 We then create a heap, which starts out with our starting node, `k`. 19 20 Next, we pop from the heap and check if we've visited the node already. 21 If so, we continue, otherwise, we know we have the minimum cost 22 to get to the node. Then, for all of its neighbors, we add it to the heap 23 with its cost + our current cost. 24 25 Finally, after traversing through all the nodes we can, if we can't 26 reach all nodes, return -1, otherwise the maximum delay time is the 27 maximum time we've encountered so far. 28 """ 29 graph = defaultdict(list) 30 31 for source, target, cost in times: 32 graph[source].append((cost, target)) 33 34 heap = [(0, k)] 35 costs = {} 36 37 while heap: 38 cost, node = heappop(heap) 39 40 if node in costs: 41 continue 42 43 costs[node] = cost 44 for neighbor_cost, neighbor in graph[node]: 45 heappush(heap, (cost + neighbor_cost, neighbor)) 46 47 if len(costs) != n: 48 return -1 49 50 return max(costs.values())
def
networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
8 def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int: 9 """ 10 This question asks us to find the shortest path to all nodes starting 11 from a given node, `k`. 12 If we cannot reach all nodes, the count of which is `n`, return -1. 13 14 This is a classic use for Dijkstra's algorithm. We first turn the graph 15 into a key value mapping of source -> (cost, target). 16 17 We do this because we want to create a min heap, required for dijkstra's. 18 We then create a heap, which starts out with our starting node, `k`. 19 20 Next, we pop from the heap and check if we've visited the node already. 21 If so, we continue, otherwise, we know we have the minimum cost 22 to get to the node. Then, for all of its neighbors, we add it to the heap 23 with its cost + our current cost. 24 25 Finally, after traversing through all the nodes we can, if we can't 26 reach all nodes, return -1, otherwise the maximum delay time is the 27 maximum time we've encountered so far. 28 """ 29 graph = defaultdict(list) 30 31 for source, target, cost in times: 32 graph[source].append((cost, target)) 33 34 heap = [(0, k)] 35 costs = {} 36 37 while heap: 38 cost, node = heappop(heap) 39 40 if node in costs: 41 continue 42 43 costs[node] = cost 44 for neighbor_cost, neighbor in graph[node]: 45 heappush(heap, (cost + neighbor_cost, neighbor)) 46 47 if len(costs) != n: 48 return -1 49 50 return max(costs.values())
This question asks us to find the shortest path to all nodes starting
from a given node, k.
If we cannot reach all nodes, the count of which is n, return -1.
This is a classic use for Dijkstra's algorithm. We first turn the graph into a key value mapping of source -> (cost, target).
We do this because we want to create a min heap, required for dijkstra's.
We then create a heap, which starts out with our starting node, k.
Next, we pop from the heap and check if we've visited the node already. If so, we continue, otherwise, we know we have the minimum cost to get to the node. Then, for all of its neighbors, we add it to the heap with its cost + our current cost.
Finally, after traversing through all the nodes we can, if we can't reach all nodes, return -1, otherwise the maximum delay time is the maximum time we've encountered so far.
def
test():