*743J Network Delay Time

743J Network Delay Time

https://leetcode.com/problems/network-delay-time/

先放一个纯净版的 Djikstra 答案

基于 PQ

// 稍微解释一下，distTo 是表示 k 到 各个点的最短路径，同时也可以作为一个 set 标记是否对该点已经访问完毕。
// PQ当中可以使用 int[] 代替 Pair. 
// relax 只是把bfs当中的操作给提出去，因为relax比较专业。
// 注意 distTo 其实是不可以省略的，在relax需要用到它防止多余的
class Solution {
    private Map<Integer, Integer> distTo;
    private PriorityQueue<Pair<Integer, Integer>> minHeap;
    private int globalMinDelayTime;
    public int networkDelayTime(int[][] edges, int n, int k) {
        this.distTo = new HashMap<>();
        this.minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        this.globalMinDelayTime = 0;
        distTo.put(k, 0);
        minHeap.offer(new Pair(k, 0));

        ArrayList<Pair<Integer, Integer>>[] adjList = buildGraph(n, edges);
        while(!minHeap.isEmpty()){
            relax(adjList, minHeap.poll());
        }
        return distTo.size() == n ? globalMinDelayTime : -1;
        
    }
    
    private ArrayList<Pair<Integer, Integer>>[] buildGraph(int numberOfNodes, int[][] edges){
        ArrayList<Pair<Integer, Integer>>[] adjList = new ArrayList[numberOfNodes + 1];
        for(int i = 1; i <= numberOfNodes; i++){
            adjList[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int from   = edge[0];
            int to     = edge[1];
            int weight = edge[2];
            adjList[from].add(new Pair(to, weight));
        }
        return adjList;
    }

    private void relax(ArrayList<Pair<Integer, Integer>>[] adjList, Pair<Integer, Integer> node){          
        int curNode = node.getKey();
        int curTime = node.getValue();
        if(distTo.getOrDefault(curNode, Integer.MAX_VALUE) < curTime) {
            return; 
        }
        globalMinDelayTime = Math.max(globalMinDelayTime, curTime); // find max minTime;
        for(Pair<Integer, Integer> edge : adjList[curNode]){
            int nextNode = edge.getKey();
            int nextTime = edge.getValue() + curTime;
            if(!distTo.containsKey(nextNode) || distTo.get(nextNode) > nextTime){
                distTo.put(nextNode, nextTime);
                minHeap.offer(new Pair(nextNode, nextTime));
            }
        }
    }
}

不基于PQ，原生Dijkstra, 只做了极小的修改，适用于稠密图，由于leetcode新加的变态稠密图用例，这个答案非常快！时间复杂度 O(V^2); 作为一个follow up是极好的。

class Solution {
    private Map<Integer, Integer> distTo;
    private Set<Integer> visited;
    private int globalMinDelayTime;
    public int networkDelayTime(int[][] edges, int n, int k) {
        this.distTo = new HashMap<>();
        this.visited = new HashSet<>();
        this.globalMinDelayTime = 0;
        distTo.put(k, 0); 
        ArrayList<Pair<Integer, Integer>>[] adjList = buildGraph(n, edges);
        // 注意，这里我们不能提前把 k 给加到 visited. 
        // 因为 有PQ的情况，visited 的活是 distTo在干，而distTo的活是PQ部分在干。
        int counter = 0; // 因为如果没有可行的路径存在，我们不存在一个更好的步骤停止循环，只好强行跳出。
        while(counter++ < n ){
            relax(adjList, visited);
        }
        return distTo.size() == n ? globalMinDelayTime : -1;
    }
    
    private ArrayList<Pair<Integer, Integer>>[] buildGraph(int numberOfNodes, int[][] edges){
        ArrayList<Pair<Integer, Integer>>[] adjList = new ArrayList[numberOfNodes + 1];
        for(int i = 1; i <= numberOfNodes; i++){
            adjList[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int from   = edge[0];
            int to     = edge[1];
            int weight = edge[2];
            adjList[from].add(new Pair(to, weight));
        }
        return adjList;
    }

    private void relax(ArrayList<Pair<Integer, Integer>>[] adjList, Set<Integer> visited){
        // 不用 PriorityQueue 的情况下，我们遍历找出还没有被访问的节点中有着最短的delay time的作为下一个节点。
        // 有PQ的时候，这一步借PQ的帮助；没有PQ的时候，我们就遍历所有的distTo来找没有被访问的节点中最短的delay time。
        // 虽然相比于用PQ来说，时间复杂度从 O(log V) 变为了 O(V).
        // 但是后面 edge 入PQ 是从 O(V log V) 变为了 O(V), 因此时间复杂度在稠密图的情况下反而提升了。
        int n = adjList.length;
        int curNode = 1;
        int curTime = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            if(visited.contains(i)) continue;
            if(distTo.containsKey(i) && distTo.get(i) < curTime){
                curNode = i;
                curTime = distTo.get(i);
            }
        }
        globalMinDelayTime = Math.max(globalMinDelayTime, curTime); // find max minTime;
        for(Pair<Integer, Integer> edge : adjList[curNode]){
            int nextNode = edge.getKey();
            int nextTime = edge.getValue() + curTime;
            if(!distTo.containsKey(nextNode) || distTo.get(nextNode) > nextTime){
                distTo.put(nextNode, nextTime);
            }
        }
        visited.add(curNode);
    }
}

下面是一些分析

这是一个并非最优化的答案

class Solution {
    private Map<Integer, Integer> distTo;
    private Map<Integer, Integer> pathTo;
    private PriorityQueue<Pair<Integer, Integer>> minHeap;
    private int globalMinDelayTime;
    private int pollOutVertexCounter;
    public int networkDelayTime(int[][] edges, int n, int k) {
        this.distTo = new HashMap<>();
        this.pathTo = new HashMap<>();
        this.minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        this.globalMinDelayTime = 0;
        minHeap.offer(new Pair(k, 0));

        ArrayList<Pair<Integer, Integer>>[] adjList = buildGraph(n, edges);
        this.pollOutVertexCounter = 0;
        int maxSize = minHeap.size();
        while(!minHeap.isEmpty()){
            relax(adjList, minHeap.poll());
            maxSize = Math.max(maxSize, minHeap.size());
        }
        System.out.println("pollOutVertexCounter: " + pollOutVertexCounter);
        System.out.println("size: " + maxSize);
        return distTo.size() == n ? globalMinDelayTime : -1;
        
    }
    
    private ArrayList<Pair<Integer, Integer>>[] buildGraph(int numberOfNodes, int[][] edges){
        ArrayList<Pair<Integer, Integer>>[] adjList = new ArrayList[numberOfNodes + 1];
        for(int i = 1; i <= numberOfNodes; i++){
            adjList[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int from   = edge[0];
            int to     = edge[1];
            int weight = edge[2];
            adjList[from].add(new Pair(to, weight));
        }
        return adjList;
    }

    private void relax(ArrayList<Pair<Integer, Integer>>[] adjList, Pair<Integer, Integer> node){          
        int curNode = node.getKey();
        int curTime = node.getValue();
        if(distTo.containsKey(curNode)) {
            return; 
        }
        pollOutVertexCounter++;
        distTo.put(curNode, curTime); // First path to curNode is the shortest path.
        globalMinDelayTime = Math.max(globalMinDelayTime, curTime); // find max minTime;
        for(Pair<Integer, Integer> edge : adjList[curNode]){
            minHeap.offer(new Pair(edge.getKey(), edge.getValue() + curTime));
        }
    }
}

这个题解有一个极大的问题，就是上面的代码并不能达到 Dijkstra 要求的时间复杂度。

考虑一个LeetCode的用例，为了简介，具体见最后。但是知道 n = 75, k = 14. 虚假的Dijkstra, 有大量的不必要的入列插入操作。 pollOutVertexCounter: 75 size: 5215 可见，虽然我们一共只从队列中提出了75次，但是入列的元素远远高于75，导致 log V 是不成立的。虽然说 log(V^2) 也不过是 2 log(V) 而已. 并且注意到此时这个例子已经是稠密图了，因而此时使用pq不一定是最好的情况。

而LC官方的答案运行的结果是： pollOutVertexCounter: 75 size: 257

为了提升这个代码的效率，我们做了如下改变，具体见评论区。总体的思想就是把进入队列之后再判断的遍历图的写法，改为了在进入队列之前就判断。为此改变了好几处的代码。

class Solution {
    private Map<Integer, Integer> distTo;
    private Map<Integer, Integer> pathTo;
    private PriorityQueue<Pair<Integer, Integer>> minHeap;
    private int globalMinDelayTime;
    private int pollOutVertexCounter;
    public int networkDelayTime(int[][] edges, int n, int k) {
        this.distTo = new HashMap<>();
        this.pathTo = new HashMap<>();
        this.minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        this.globalMinDelayTime = 0;
        distTo.put(k, 0);   // 把代码改为进入pq之前先初始化好。
        minHeap.offer(new Pair(k, 0));

        ArrayList<Pair<Integer, Integer>>[] adjList = buildGraph(n, edges);
        this.pollOutVertexCounter = 0;
        int maxSize = minHeap.size();
        while(!minHeap.isEmpty()){
            relax(adjList, minHeap.poll());
            maxSize = Math.max(maxSize, minHeap.size());
        }
        System.out.println("pollOutVertexCounter: " + pollOutVertexCounter);
        System.out.println("size: " + maxSize);
        return distTo.size() == n ? globalMinDelayTime : -1;
        
    }
    
    private ArrayList<Pair<Integer, Integer>>[] buildGraph(int numberOfNodes, int[][] edges){
        ArrayList<Pair<Integer, Integer>>[] adjList = new ArrayList[numberOfNodes + 1];
        for(int i = 1; i <= numberOfNodes; i++){
            adjList[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int from   = edge[0];
            int to     = edge[1];
            int weight = edge[2];
            adjList[from].add(new Pair(to, weight));
        }
        return adjList;
    }

    private void relax(ArrayList<Pair<Integer, Integer>>[] adjList, Pair<Integer, Integer> node){          
        int curNode = node.getKey();
        int curTime = node.getValue();
        if(distTo.getOrDefault(curNode, Integer.MAX_VALUE) < curTime) {
            return; 
            // 这里由 distTo.containsKey(curNode) 改过来，
            // 是因为由于我们的写法是入列之前就在distTo中记录了数据。
            // 我们需要放过curNode, curTime本身进入本次relax的情况，而排除别的情况，因此只能这么写。 
        }

        pollOutVertexCounter++;
        globalMinDelayTime = Math.max(globalMinDelayTime, curTime); // find max minTime;
        for(Pair<Integer, Integer> edge : adjList[curNode]){
            int nextNode = edge.getKey();
            int nextTime = edge.getValue() + curTime;
            // 这里我们改为不无脑进入队列，而是先判断再决定是否进入。
            if(!distTo.containsKey(nextNode) || distTo.get(nextNode) > nextTime){
                distTo.put(nextNode, nextTime);
                minHeap.offer(new Pair(nextNode, nextTime));
            }
        }
    }
}

下面的这种写法也还是不行，虽然比无脑进pq要强一点：

pollOutVertexCounter: 75 size: 2653

class Solution {
    private Map<Integer, Integer> distTo;
    private PriorityQueue<Pair<Integer, Integer>> minHeap;
    private int globalMinDelayTime;
    private int pollOutVertexCounter;
    public int networkDelayTime(int[][] edges, int n, int k) {
        this.distTo = new HashMap<>();
        this.minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        this.globalMinDelayTime = 0;

        minHeap.offer(new Pair(k, 0)); // 注意这里我们没有初始化 distTo

        ArrayList<Pair<Integer, Integer>>[] adjList = buildGraph(n, edges);
        this.pollOutVertexCounter = 0;
        int maxSize = minHeap.size();
        while(!minHeap.isEmpty()){
            relax(adjList, minHeap.poll());
            maxSize = Math.max(maxSize, minHeap.size());
        }
        System.out.println("pollOutVertexCounter: " + pollOutVertexCounter);
        System.out.println("size: " + maxSize);
        return distTo.size() == n ? globalMinDelayTime : -1;
        
    }
    
    private ArrayList<Pair<Integer, Integer>>[] buildGraph(int numberOfNodes, int[][] edges){
        ArrayList<Pair<Integer, Integer>>[] adjList = new ArrayList[numberOfNodes + 1];
        for(int i = 1; i <= numberOfNodes; i++){
            adjList[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            int from   = edge[0];
            int to     = edge[1];
            int weight = edge[2];
            adjList[from].add(new Pair(to, weight));
        }
        return adjList;
    }

    private void relax(ArrayList<Pair<Integer, Integer>>[] adjList, Pair<Integer, Integer> node){          
        int curNode = node.getKey();
        int curTime = node.getValue();
        if(distTo.containsKey(curNode)) {
            return;  
        }
        distTo.put(curNode, curTime);
        pollOutVertexCounter++;
        globalMinDelayTime = Math.max(globalMinDelayTime, curTime); // find max minTime;
        for(Pair<Integer, Integer> edge : adjList[curNode]){
            int nextNode = edge.getKey();
            int nextTime = edge.getValue() + curTime;
            if(!distTo.containsKey(nextNode)){
                minHeap.offer(new Pair(nextNode, nextTime));
            }
        }
    }
}

2020 写的 Dijkstra 算法

这个题一度被标记为简单，因为就是Dijkstra. 当然我并不会Dijkstra，因为准备太匆忙就上马刷题了。不过发现很多人也不会。可以这本应当是科班的标配，可见大多数人都不想读书。

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        //这个题是很经典的 Dijkstra 算法，是一个BFS。
        //应当学习Dijkstra
        //这个题的频率不高 但是像谷歌之类的就爱考。
        // Integer 用来存 id, 
        // List<int[]> 用来保存所有的从这一点出发去到到点 以及距离。
        // 因此int[]里有两个元素 [1] 是 distance，[0]是 node
        Map<Integer,List<int[]>> graph = new HashMap<>();
        // 把所有的edge都记录下来
        for(int[] edge : times){
            int id = edge[0];
            int[] data = new int[]{edge[1],edge[2]};
            if(!graph.containsKey(edge[0])){
                graph.put(id, new ArrayList<int[]>());
            }
            graph.get(id).add(data);
        }
        
        //创建一个最小堆，其实默认就是最小堆 
        // 如果改成最大堆，那么就是找最长路径的算法。
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>( (info1, info2) -> info1[0] - info2[0] );
        //堆里 [0]是distance，[1]是node id 初始化
        heap.offer(new int[]{0,K});
        
        // dist用来储存某个node离储存离选定节点的(最小)距离。
        // key是node, val是距离。
        // 如果dist不能取到所有的节点，说明有路不通。
        Map<Integer, Integer> dist = new HashMap<>();
        
        while(!heap.isEmpty()){ // 直到全部出列才停止。
            //取出目前距离最短的父节点和它到目标节点的距离
            int[] info = heap.poll();
            int distFather = info[0];
            int nodeFather = info[1];
            
            //如果已经在dist中记录过了 就跳过
            //这里跳过很重要，因为优先队列保证了，同一个节点，先进入的
            //一定是距离更短的那个组合。比如 3,A 一定比 4,A 先入列。
            if(dist.containsKey(nodeFather))  continue;
            
            //没有记录过 就把该点加进去，第一个是K,0 自己
            dist.put(nodeFather,distFather);
            
            //如果从这个父点出发有graph的路线
            if(graph.containsKey(nodeFather)){
            //那么就从这个node出发的所有路线都遍历
                for(int[] edge: graph.get(nodeFather)){
                    //目标node 和距离 命名为子节点和到父节点的距离
                    int nodeSon = edge[0];
                    int distSon  = edge[1];
                    //如果这个节点未被访问过，把它加上，距离当然是父子之和
                    if(!dist.containsKey(nodeSon)){
                        heap.offer(new int[]{distFather+distSon,nodeSon});
                    }
                }
            }
        }
        
        if(dist.size()!=N) return -1;
        int ans = 0;
        for(int cand : dist.values()){
            ans = Math.max(ans,cand);
        }
        return ans;
    }
}

LeetCode 那个极端的用例

一个 LeetCode 的测试用例，非常稠密的图。 n = 75, k = 14;

Previous735. Asteroid-Collision Next763. Partition-Labels

Last updated 2 years ago

Was this helpful?