Leetcode: Network Delay Time

Network Delay Time



Similar Problems:


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.

Note:

  1. N will be in the range [1, 100].
  2. K will be in the range [1, N].
  3. The length of times will be in the range [1, 6000].
  4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/network-delay-time
// Basic Ideas: BFS
// Complexity: Time O(1), Space O(1)
//           max caculation: 100*100
//           max space = max(len(times), N)
func networkDelayTime(times [][]int, N int, K int) int {
    visited := map[int]bool{}
    res := 0
    edges := map[int][][]int{}
    for _, t := range times {
        node := t[0]
        edges[node] = append(edges[node], []int{t[1], t[2]})
    }
    queue := [][]int{[]int{K, 0}}
    index, min := 0, 0
    for len(queue) != 0 {
        visited[queue[index][0]] = true
        res += min
        if len(visited) == N {
            return res
        }

        m := map[int]int{}
        // deduct time
        for i, item := range queue {
            if i == index { continue }
            m[item[0]] = item[1] - min
        }

        // add adjacent node
        for _, item := range edges[queue[index][0]] {
            if !visited[item[0]] {
                _, ok := m[item[0]]
                if !ok || m[item[0]] > item[1] {
                    m[item[0]] = item[1]
                }
            }
        }
        // add to list
        min = 1<<31 - 1
        queue = [][]int{}
        i := 0
        for node := range m{
            if m[node] < min {
                index, min = i, m[node]
            }
            queue = append(queue, []int{node, m[node]})
            i++
        }
    }
    return -1
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.