leetcode_gym/_problems/networkDelayTime.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Network Delay Time	2020-06-19	graph, dijkstra	https://leetcode.com/problems/network-delay-time	Attempted

Problem

There are N network nodes, labelled 1 to N.

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.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.


Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Solution

Dijkstra is written very similar to BFS but with weights.

The end result of this problem is an array that keeps track of elaped time.

        node     0,1,2,3,4  <-- index corresponds to node
elapsedTime:    [0,1,0,1,2] <-- value corresponds to time for signal to reach node i from node K (ie: takes 2 seconds to reach node 4 from node 2)

{% highlight python %}

import heapq from collections import deque from collections import defaultdict

times = 2,1,1],[2,3,1],[3,4,1 N = 4 K = 2

def networkDelayTime(times, N, K):

elapsedTime = [0] + [float("inf")] * N
graph = defaultdict(list)
heap = [(0, K)]     # time, start node (ie: (0,2))

# add to adj hash table, where values = (edge,weight)
for u, v, w in times:
    graph[u].append((v, w))

'''
    graph:
    2: [(1,1),(1,3)]
    3: [(4,1)]
'''

while heap:

    # pop off heap/queue
    time, node = heapq.heappop(heap)
    if time < elapsedTime[node]:

        # process (add to elapsed time array)
        elapsedTime[node] = time

        # add neighbours, include weight
        for v, w in graph[node]:
            heapq.heappush(heap, (time + w, v))     # at node 3, add neighbour 4 (time+w, v)=(1+1,4) and heap=[(2,4)] -> time to reach node 4=2


mx = max(elapsedTime)
return mx if mx < float("inf") else -1

print( networkDelayTime(times, N, K) )

{% endhighlight %}