Leetcode 743网络延迟时间

743网络延迟时间

不难发现，实际上求网络的延迟时间就是求节点k到其他各个节点的最短路径，在最短路径中找到一个最大值，就可以得到网络的延迟时间。

求一个顶点到其他顶点的最短路径，常用的一种算法的Dijkstra算法

算法的主要思想如下：

下面通过一个具体的例子来看Dijsktra算法的实际过程：

二、朴素版Dijkstra算法

1、使用邻接矩阵来存储图

class Solution {
private:
    static const int N = 110, INF = 0x3f3f3f3f;//使用INF来表示(i,j)之间不存在边
    int n, G[N][N], dist[N];
    bool visited[N] = {false};
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        this->n = n;
        memset(G, 0x3f, sizeof(G));
        for (vector<int> nums : times){
            int u = nums[0], v = nums[1], w = nums[2];
            G[u][v] = w;
        }
        Dijkstra(k);
        int res = -1;
        for (int i = 1; i <= n; i++)  res = max(res, dist[i]);
        return res == INF ? -1 : res;
    }

    void Dijkstra(int k){
        memset(dist, 0x3f, sizeof(dist));
        dist[k] = 0;
        for (int i = 0; i < n; i++){
            int u = -1, MIN = INF;
            for (int j = 1; j <= n; j++){
                if (!visited[j] && dist[j] < MIN){
                    u = j;
                    MIN = dist[j];
                }
            }
            if (u == -1)    return ;
            visited[u] = true;
            for (int v = 1; v <= n; v++){
                if (!visited[v] && G[u][v] != INF && dist[u] + G[u][v] < dist[v]){
                    dist[v] = dist[u] + G[u][v];
                }
            }   
        }
    }
};

2、使用邻接表来存储图

class Solution {
private:
    static const int N = 110, INF = 0x3f3f3f3f;
    int n, dist[N];
    bool visited[N] = {false};
    vector<pair<int, int>> Adj[N];
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        this->n = n;
        for (vector<int> nums : times){
            int u = nums[0], v = nums[1], w = nums[2];
            Adj[u].push_back({w, v});
        }
        Dijkstra(k);
        int res = -1;
        for (int i = 1; i <= n; i++)    res = max(res, dist[i]);
        return res == INF ? -1 : res;
    }

    void Dijkstra(int k){
        memset(dist, 0x3f, sizeof(dist));
        dist[k] = 0;
        for (int i = 0; i < n; i++){
            int u = -1, MIN = INF;
            for (int j = 1; j <= n; j++){
                if ( !visited[j] && dist[j] < MIN){
                    u = j;
                    MIN = dist[j];
                }
            }
            if (u == -1)    return ;
            visited[u] = true;
            for (int i = 0; i < Adj[u].size(); i++){
                int v = Adj[u][i].second, w = Adj[u][i].first;
                if (!visited[v] && dist[u] + w < dist[v]){
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

    
};

三、堆优化版Dijkstra

1、邻接矩阵

class Solution {
private:
    static const int N = 110, INF = 0x3f3f3f3f;
    int n, G[N][N], dist[N];
    bool visited[N] = {false};
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        this->n = n;
        memset(G, 0x3f, sizeof(G));
        for (vector<int> nums : times){
            int u = nums[0], v = nums[1], w = nums[2];
            G[u][v] = w;
        }
        Dijkstra(k);
        int res = -1;
        for (int i = 1; i <= n; i++)  res = max(res, dist[i]);
        return res == INF ? -1 : res;
    }

    void Dijkstra(int k){
        memset(dist, 0x3f, sizeof(dist));
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
        dist[k] = 0;
        pq.push({0, k});
        while(pq.size()){
            int u = pq.top().second, w = pq.top().first;
            pq.pop();
            if (visited[u]) continue;
            visited[u] = true;
            for (int v = 1; v <= n; v++){
                if (!visited[v] && G[u][v] != INF && dist[u] + G[u][v] < dist[v]){
                    dist[v] = dist[u] + G[u][v];
                    pq.push({dist[v], v});
                }
            }
        }
    }

    
};

2、邻接表

class Solution {
private:
    static const int N = 110, INF = 0x3f3f3f3f;
    int n, dist[N];
    bool visited[N] = {false};
    vector<pair<int, int>> Adj[N];
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        this->n = n;
        for (vector<int> nums : times){
            int u = nums[0], v = nums[1], w = nums[2];
            Adj[u].push_back({w, v});
        }
        Dijkstra(k);
        int res = -1;
        for (int i = 1; i <= n; i++)    res = max(res, dist[i]);
        return res == INF ? -1 : res;
    }

    void Dijkstra(int k){
        memset(dist, 0x3f, sizeof(dist));
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
        dist[k] = 0;
        pq.push({0, k});
        while(pq.size()){
            int u = pq.top().second, w = pq.top().first;
            pq.pop();
            if (visited[u]) continue;
            visited[u] = true;
            for (int i = 0; i < Adj[u].size(); i++){
                int v = Adj[u][i].second, w = Adj[u][i].first;
                if (!visited[v] && dist[u] + w < dist[v]){
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    
};

总结：在这里题目所给的数据范围比较小，所以上面四种代码的时间相差不大