Leetcode/Lintcode

Leetcode 743. Network Delay Time

Description

Origin 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.

Example

Example

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

Solution

By observation, we can tell this is a single-source shortest-path problem. So we can simply implement the Dijkstra’s algorithm to solve the problem.

Here is my code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import defaultdict
from heapq import heappush, heappop

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        neighbors = defaultdict(list)
        nodes = [i+1 for i in range(N)]
        for u, v, w in times:
            neighbors[u].append((v,w))
        
        # set all nodes' dis to inf
        dist = {node:float("inf") for node in nodes}
        dist[K] = 0 # set the dis of start node to 0
        
        queue = [(0, K)]
        while queue:
            d, cur = heappop(queue)
            
            for nei, w in neighbors[cur]:
                if dist[cur] + w < dist[nei]:
                    dist[nei] = dist[cur] + w
                    queue.append((dist[nei], nei))
                    
        result = max(dist.values())
        return result if result != float("inf") else -1 # return -1 if it is impossible

Analysis

The time complexity is O(E logE) since we use a heap to perform the Dijkstra.

Visit my Visualizer page for intuitive visualization of the Dijkstra's algorithm.