Blackops

初心易得，始终难守

0%

SPFA的SLF和LLL优化

发表于 更新于 分类于 ， ，

最近学了下$SPFA$的两个优化，感觉效果确实有，代码也简单，但是感觉一般不会卡$SPFA$

$SLF$(Small Label First)优化：

假设当前队列的队头点为$front​$，拓展出去的点为$v​$，如果更新后$dis[v] \lt dis[front]​$，那很可能$v​$比$front​$更有潜力，因此把$v​$点放到队列的头部而不是尾部，因此这里我们所说的队列指的是滋瓷前后都可以插入数据的双端队列$std::deque​$

$SLF$代码：

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
void spfa(int s)
{
    deque<int>Q;
    CLR(d, INF);
    CLR(vis, false);
    d[s] = 0;
    vis[s] = 1;
    Q.push_back(s);
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop_front();
        vis[u] = 0;
        for (int i = head[u]; ~i; i = E[i].nxt)
        {
            int v = E[i].to;
            if (d[v] > d[u] + E[i].d)
            {
                d[v] = d[u] + E[i].d;
                if (!vis[v])
                {
                    vis[v] = 1;
                    //SLF优化
                    if (!Q.empty() && d[v] < d[Q.front()])
                        Q.push_front(v);
                    else
                        Q.push_back(v);
                    //SLF优化
                }
            }
        }
    }
}

 
 

$LLL$(Large Label Last)优化：

假设当前从队列取出的点为$u$，如果当前点$u$到源点$S$的距离$dis[u]$小于队列$Q$中所有点的距离平均值${\sum{dis[i]}} \over |Q|$，即$dis[u]*|Q| \lt \sum\limits_{i \in Q}{dis[i]}$（在代码实现上把这个判定式子转换成乘法判断会更简单），那么就将$u$放到队列末尾，直到找到一个点$x$比平均值要小，再从$x$开始拓展更新，这个优化感觉效果一般，似乎不如代码简洁的$SLF$，有时候甚至比普通的$SPFA​$都慢
"Jianjie"

$LLL$代码：

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
void spfa(int s)
{
    deque<int>Q;
    CLR(d, INF);
    CLR(vis, false);
    d[s] = 0;
    vis[s] = 1;
    Q.push_back(s);
    LL qsz = 1, sum = 0;//LLL
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop_front();
        //LLL优化
        if ((LL)d[u] * qsz >= sum)
        {
            Q.push_back(u);
            continue;
        }
        --qsz;
        sum -= d[u];
        //LLL优化
        vis[u] = 0;
        for (int i = head[u]; ~i; i = E[i].nxt)
        {
            int v = E[i].to;
            if (d[v] > d[u] + E[i].d)
            {
                d[v] = d[u] + E[i].d;
                if (!vis[v])
                {
                    vis[v] = 1;
                    
                    //SLF优化
                    if (!Q.empty() && d[v] < d[Q.front()])
                        Q.push_front(v);
                    else
                        Q.push_back(v);
                    //SLF优化
                    
                    //LLL优化
                    ++sz;
                    sum += (LL)d[v];
                    //LLL优化
                }
            }
        }
    }
}