Network Delay Time

描述

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 1:

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

Note:

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

分析

本题可以抽象为：给定图 G 和源顶点 v，找到从 v 至图中所有顶点的最短路径。这是经典的单源最短路径问题，用 Dijkstra 算法。时间复杂度 $O(E\log V)$，空间复杂度 $O(V+E)$，V 为顶点个数，E 为边条数。

代码

Python

// Network Delay Time
// Dijkstra
// Time Complexity: O(ElogN), Space Complexity: O(N + E)
class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // adjacency list, map<vertex_id, map<vertex_id, weight>>
        Map<Integer, Map<Integer,Integer>> graph = new HashMap<>();
        for(int[] time : times){
            graph.putIfAbsent(time[0], new HashMap<>());
            graph.get(time[0]).put(time[1], time[2]);
        }

        Map<Integer, Integer> dist = dijkstra(graph, K);

        return dist.size() == N ? Collections.max(dist.values()) : -1;
    }

    /** Standard Dijkstra algorithm.
     *
     @param graph Adjacency list, map<vertex_id, map<vertex_id, weight>>.
     @param start The starting vertex ID.
     @return dist, map<vertex_id, distance>.
     */
    private static Map<Integer, Integer> dijkstra(Map<Integer, Map<Integer,Integer>> graph, int start) {
        // map<vertex_id, distance>
        Map<Integer, Integer> dist = new HashMap<>();
        // vertex_id -> father_vertex_id
        Map<Integer, Integer> father = new HashMap<>();

        // pair<distance, vertex_id>, min heap, sorted by distance from start to vertex_id
        Queue<Pair<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> a.getKey() - b.getKey());

        // from start to start itself
        pq.offer(new Pair(0, start));
        dist.put(start, 0);

        while(!pq.isEmpty()){
            final int u = pq.poll().getValue();
            if (!graph.containsKey(u)) continue; // leaf node

            for(int v : graph.get(u).keySet()){
                final int w = graph.get(u).get(v);
                if (!dist.containsKey(v) || dist.get(u)+ w < dist.get(v)) {
                    final int shorter = dist.get(u)+ w;
                    dist.put(v, shorter);
                    father.put(v, u);
                    pq.offer(new Pair(shorter, v));
                }
            }
        }

        return dist;
    }
}

Java

// TODO

C++

# Network Delay Time
# Dijkstra
# Time Complexity: O(ElogN), Space Complexity: O(N + E)
class Solution:
    def networkDelayTime(self, times: list[list[int]], N: int, K: int) -> int:
        # adjacency list, map<vertex_id, map<vertex_id, weight>>
        graph = {}
        for u, v, w in times:
            if u not in graph:
                graph[u] = {}
            graph[u][v] = w

        dist = self.dijkstra(graph, K)

        return max(dist.values()) if len(dist) == N else -1

    def dijkstra(self, graph: dict, start: int) -> dict:
        """Standard Dijkstra algorithm.

        Args:
            graph: Adjacency list, map<vertex_id, map<vertex_id, weight>>.
            start: The starting vertex ID.
        Returns:
            dist: map<vertex_id, distance>.
        """
        # map<vertex_id, distance>
        dist = {}
        # vertex_id -> father_vertex_id
        father = {}

        # pair<distance, vertex_id>, min heap, sorted by distance from start to vertex_id
        pq = [(0, start)]
        dist[start] = 0

        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            if u not in graph:  # leaf node
                continue

            for v, w in graph[u].items():
                if v not in dist or dist[u] + w < dist[v]:
                    shorter = dist[u] + w
                    dist[v] = shorter
                    father[v] = u
                    heapq.heappush(pq, (shorter, v))

        return dist

相关题目

• Path with Maximum Probability