堆优化的迪杰斯特拉算法 - 社交网络图中结点的“重要性”计算_社交网络紧密度中心性迪杰斯特拉算法

这是一道来自PAT的算法与数据结构的练习题。原题链接：7-36 社交网络图中结点的“重要性”计算。

借这道题讲讲堆优化的迪杰斯特拉算法怎么写。

首先解读下题目，题目很长啊，不过有用的话就一句：结点$v​i$的“紧密度中心性”$Cc(v​i​​)$数学上定义为$v​i$到其余所有结点$v​j(j≠i)$ 的最短距离$d(v​i ,v​j)$的平均值的倒数。因此，这是个最短路问题，而且图中可能存在环。

数据规模：点$N < 10^4$，边$M < 10^5$，询问次数$K<10^2$。弗洛伊德算法(时间复杂度$O(n^3)$)不用考虑，而求单源最短路径的算法就剩下迪杰斯特拉、$Bellman$、$SPFA$，而$Bellman$、$SPFA$的复杂度和边的规模有关，这题中的边比点多，因此不宜使用，故只能使用迪杰斯特拉算法了。

而迪杰斯特拉算法的时间复杂度为$O(n^2)$，n是点数。如果直接使用，总的复杂度为$O(kn^2)$达到了$10^{10}$，显然是不能接受的，因此只能用堆去优化迪杰斯特拉算法。

普通迪杰斯特拉算法的思想需要明白，不明白的可以看我之前的博客Dijkstra或者网上其他人的博客。

给出普通迪杰斯特拉的算法代码：

#define Inf 0xfffffff    //无穷大
#define Maxn 1005

int map[Maxn][Maxn];    //邻接矩阵
int dis[Maxn];            //最短路径
int visit[Maxn];        //是否求得最短路径

void dij(int tag)
{
    //Init
    memset(visit,0,sizeof(visit));
    int i;
    for(i=1;i<=n;i++)
        dis[i]=map[tag][i];
    visit[tag]=1;
    //一个点一个点，直到visit都为1
    for(i=1;i<n;i++)
    {
        int temp=Inf;
        int k=tag;
        int j;
        //找最短的
        for(j=1;j<=n;j++)
            if(temp>dis[j]&&!visit[j])
                temp=dis[j],k=j;
        visit[k]=1;
        //松弛
        for(j=1;j<=n;j++)
            if(dis[j]>dis[k]+map[k][j]&&!visit[j])
                dis[j]=dis[k]+map[k][j];
    }
}
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

可以看出找最短的dis[j]和松弛这两个操作时间复杂度为$O(n)$，这里把查找最短的dis[j]用堆去实现，可以优化到$O(logn)$；

堆优化的迪杰斯特拉算法，采用优先队列的$bfs$实现，每次都队列中找到最短的dis，用对应结点去松弛其他点，把成功松弛过的点又加入到队列，让这些点成为候选的最短dis。

由于对领接表存储的图进行$bfs$的时间复杂度为$O(n + e)$，而优先队列弹出队头元素的时间复杂度为$O(logn)$，由于每一个点都要被弹出队列一次，故堆优化的迪杰斯特拉的时间复杂度为$O(nlogn)$。

对于这个题目来说，堆优化过后总的时间复杂度为$O(knlogn)$达到了$10^6$，在2s的时限内是可以接受的。

下面是堆优化迪杰斯特拉算法的模板：

void dijstra(int src)
{
    vector<bool> used(n + 1, false);
    d.clear();
    d.resize(n + 1, INF);
    d[src] = 0;
    priority_queue<Node> que;
    que.emplace(src, d[src]);
    while (!que.empty()) {
        auto now = que.top();
        que.pop();
        used[now.id] = true;
        d[now.id] = now.val;
        for (int i = head[now.id]; i + 1; i = edges[i].next)
            if (!used[edges[i].to] && d[edges[i].to] > d[now.id] + 1)
                d[edges[i].to] = d[now.id] + 1,
                que.emplace(edges[i].to, d[edges[i].to]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

最后给出这个题的完整代码：

#include <bits/stdc++.h>

using namespace std;

typedef struct tagEdge Edge;

const int INF = 0x3f3f3f30;

struct tagEdge {
    int to, next;
    tagEdge() {}
    tagEdge(int to, int next) : to(to), next(next) {}
};

struct Node {
    int id, val;
    Node() {}
    Node(int id, int val) : id(id), val(val) {}
    bool operator < (const Node &other) const {
        return val > other.val;
    }
};

struct Solution {
    int n, m;
    vector<int> head;
    vector<Edge> edges;
    vector<int> d;

    vector<int> question;

    Solution(int n, int m);
    void addEdge(int x, int y, int i);
    void dijstra(int src);
    void work();
};

void Solution::addEdge(int x, int y, int i)
{
    edges.emplace_back(y, head[x]);
    head[x] = i;
}

Solution::Solution(int n, int m)
{
    this->n = n;
    this->m = m;
    head.resize(n + 1, -1);
    for (int i = 0; i < 2 * m; i += 2) {
        int x, y;
        cin >> x >> y;
        addEdge(x, y, i);
        addEdge(y, x, i + 1);
    }
    int k, x;
    for (cin >> k; k; k--)
        question.push_back((cin >> x, x));
    d.resize(n + 1, INF);
}

void Solution::dijstra(int src)
{
    vector<bool> used(n + 1, false);
    d.clear();
    d.resize(n + 1, INF);
    d[src] = 0;
    priority_queue<Node> que;
    que.emplace(src, d[src]);
    while (!que.empty()) {
        auto now = que.top();
        que.pop();
        used[now.id] = true;
        d[now.id] = now.val;
        for (int i = head[now.id]; i + 1; i = edges[i].next)
            if (!used[edges[i].to] && d[edges[i].to] > d[now.id] + 1)
                d[edges[i].to] = d[now.id] + 1,
                que.emplace(edges[i].to, d[edges[i].to]);
    }
}

void Solution::work()
{
    dijstra(1);
    bool f = true;
    for (int i = 1; i <= n; i++)
        if (d[i] == INF) {
            f = false;
            break;
        }
    if (!f) {
        for (auto ele : question)
            printf("Cc(%d)=0.00\n", ele);
        return ;
    }
    for (auto ele : question) {
        dijstra(ele);
        double ans = 0;
        for (int i = 1; i <= n; i++)
            ans += d[i];
        ans = (double)(n - 1) / ans;
        printf("Cc(%d)=%.2f\n", ele, ans);
    }
}

int main()
{
    int n, m;
    while (cin >> n >> m) {
        Solution solution(n, m);
        solution.work();
    }
    return 0;
}
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
102
103
104
105
106
107
108
109
110
111
112
113
114