Leetcode 743 Network Delay Time

题意：给定n个节点的网络，以及节点之间传输的时间，求从节点k出发传输信息，最少需要多久，所有的节点都能够接收到信息

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

题解：给定一个有向图以及节点之间的权重，求从一个节点出发，到所有节点的最短路径。到所有节点的最短路径的最大值就是答案。
可以用dijikstra算法。
该算法的原理是，从给定的节点 $x$ 出发，优先处理距离最短的节点 $y$ ，并且根据节点 $y$ 更新于与 $y$ 相邻的那些点的距离
请添加图片描述比如这题我从节点2出发，发现2能到1和3，由于此处2到1和3的距离一样，所以优先处理哪个节点都可以，这里取1，那1的最短路就定下来了，没有节点和1相连所以不用更新距离信息。然后处理节点3，2到3的距离确定，3还可以到4，那2到4的节点距离就确定下来了，以此类推。

然后此处是用小顶堆来实现。先根据给定的条件建图。比如[2, 1, 1]可以建立成 ${2: <1, 1>,<3, 2>}$ ，代表从节点2出发，到1的距离为1，到2的距离为2（距离在前的话我不用修改小顶堆的函数）

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    	//建图
        unordered_map<int, vector<pair<int,int>>> g;
        for (auto time : times) {
            g[time[0]].push_back({time[2], time[1]});
        }
        
        //建立距离矩阵，代表从节点k到每一个节点的距离
        vector<int> d(n+1, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
        //初始化，节点k到自己的距离为0，并且q中放入节点
        d[k] = 0;
        q.push({0, k});

        while(q.size()) {
            auto [dist, node] = q.top();
            q.pop();
            //如果发现得到的距离距离大，那就不用计算这个pop出来的节点了，注意这里还方便的把dijikstra算法中的vis数组拿掉了，如果说节点没vis过那d[node]为INT_MAX
            if(dist > d[node]) continue;
            //计算点k到node的邻居的距离，并把这些邻居放入q中
            for(auto [distance,next] : g[node]) {
                if( distance + d[node] < d[next] ) {
                    d[next] = distance + d[node];
                    q.push({d[next], next});
                }
            }
        }
        //求解最大值
        int res = 0;
        for(int i = 1; i < d.size(); i++) {
                if ( d[i] == INT_MAX) return -1;
                res = max(res, d[i]);
        }
        return res;
    }
};

时间复杂度 $O ((V + E) l o g V)$
入队操作时 $O (l o g V)$ ,每个节点都入队一次，这些节点对应的每条边也入队一次，所以加起来就是 $O ((V + E) l o g V)$
空间复杂度 $O (V + E)$

秒客网

Leetcode 743 Network Delay Time

相关文章