Leetcode:743. Network Delay Time

Posted on | Edited on | Comments: | Views:
Graph Heap Dijkstra

743. Network Delay Time

题目理解:

给出一个有向边权集, 计算遍历全部节点所用的时间, 无法完全遍历则返回-1

思路:

基本是实现了一下Dijkstra算法而已, 它是解决无负权边单源最短路径的常用算法之一.
Dijkstra算法介绍

    1. 取distance队列中路径最短的结点v
    1. 访问v的连通边, 更新与v连通的结点的最短路径与distance队列
    1. 重复1 2

小结:

算法课的图进行到第二部分, 找出单源图的最短路, 就是学习Dijkstra算法.
其中优先队列有多种实现方法, 比较简单的就是直接用数组, 每次更新需要O(n)遍历, 复杂度较高; 或者是用堆, 更新消耗可以降低到O(log(n)); 或者其他方法.
这里使用堆来实现的优先队列.
总的时间复杂度为 O((|V|+|E|)*log(V))

Submission Detail:

Detail

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <vector>
#include <map>
#include <iostream>
using namespace std;
class Solution {
public:
    int runTime;
    map<int, int> timeMap[110];
    vector<vector<int>> edges;
    vector<int> dis;
    vector<int> que;
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        edges.clear();
        runTime = 0;

        // 构造图的邻接表
        edges.push_back(vector<int>());
        dis.push_back(6001);
        for (int i = 1; i <= N; i++) {
            edges.push_back(vector<int>());
            dis.push_back(6001);
            que.push_back(i);
        }
        dis[K] = 0;
        
        // 记录图的权重
        for (auto i:times) {
            edges[i[0]].push_back(i[1]);
            timeMap[i[0]][i[1]] = i[2];
        }

        // initial the heap queue
        initialHeap();

        Dijkstra();

        return runTime==6001?-1:runTime;
    }

    void Dijkstra() {
        // 队列不为空时, 更新路径
        while (que.size() > 0) {
            int now = que[0];
            runTime = dis[que[0]];
            que[0] = que[que.size()-1];
            que.pop_back();
            heapize(0);
    
            // 遍历边, 若小于dis[]则更新
            for (auto i:edges[now]) {
                if (timeMap[now].count(i) && dis[i] > dis[now] + timeMap[now][i]) {
                    dis[i] = dis[now] + timeMap[now][i];
                    initialHeap();
                }
            }
        }
    }
    
    // 初始化堆
    void initialHeap() {
        for (int i = que.size()/2-1; i >= 0; --i) {
            int left = (i*2+1>que.size()-1)?que.size()-1:i*2+1;
            int right = (i*2+2>que.size()-1)?que.size()-1:i*2+2;
            if (dis[que[i]] > dis[que[left]] || dis[que[i]] > dis[que[right]]) {
                if (dis[que[left]] < dis[que[right]]) {
                    int t = que[i];
                    que[i] = que[left];
                    que[left] = t;
                    heapize(left);
                } else {
                    int t = que[i];
                    que[i] = que[right];
                    que[right] = t;
                    heapize(right);
                }
            }
        }
    }
    
    // 递归堆化
    void heapize(int x) {
        if (x > que.size()/2-1 || que.size() == 0) {
            return;
        }
        int left = (x*2+1>que.size()-1)?que.size()-1:x*2+1;
        int right = (x*2+2>que.size()-1)?que.size()-1:x*2+2;
        if (dis[que[x]] > dis[que[left]] || dis[que[x]] > dis[que[right]]) {
            if (dis[que[left]] < dis[que[right]]) {
                int t = que[x];
                que[x] = que[left];
                que[left] = t;
                heapize(left);
            } else {
                int t = que[x];
                que[x] = que[right];
                que[right] = t;
                heapize(right);
            }
        }
    }
};