关于dijkstra判断负环的思考

发表于 | 分类于

首先介绍dijkstra和spfa两者的实现思路

参考博客：戳这里

djkstra

Dijkstra是一种求单源最短路的基础算法，时间复杂度在不加堆优化的情况下是o(n^2)的，加了堆优化就能简化到o(nlogn)，而且算法稳定性很强（从这点上来说比SPFA好多了，具体怎么好下面再讲），基础思路如下：

　　首先，把所有点到源的距离设为最大，然后把源加入队列，接着每次对队列首做这种操作：用邻接表找到从这个点能链到的所有所有点，接着要按大小顺序找当前距离和当前队首最近的点（这个按大小顺序就是可以用堆优化的地方），做松弛操作，松弛成功，将这个点入队，否则按大小顺序找下一条边，然后重复做松弛操作，直到当前点所有能链到的边松弛过，弹出当前点，重复以上操作，直到队列里没有其他元素。结束程序，输出单源到某点距离。

spfa

SPFA算法全称是Shortest Path Faster Algorithm算法，人家都叫“Faster”了，那肯定有过人之处，基础思路如下：

　　首先，还是把所有点到源的距离设为最大，把源加入队列，接着每次对队首做这种操作：用邻接表找到从这个点能链到的所有所有点，然后对每条边做松弛操作，只要松弛成功，我们就判断当前松弛成功的点是否在队列，如果不在，就入队，否则就只是做松弛，然后弹出当前点，对下一点再次做以上操作，直到队列为空。

所以我们可以看出，用队列实现的spfa其实和广搜没什么区别，都是把一个点放进去，再把能与之相邻的点全部放进去（只不过加了松弛操作这个条件）。可以预知稠密图下该算法的时间复杂度会多高。。。而spfa判断负环的思路也很简单，一个点最多连n-1个点，如果这个点入队n次，那肯定是因为有负环了。（类比广搜）

然而大家都知道，堆优化的djkstra与普通的djkstra相比，可以去掉点标记。那么这样的dijkstra能不能判断负环，这引起了我的思考。

这里举出一个典型的样例：

无向图

1 2 3

1 3 2

2 3 -3

这是个负环，而堆优化的dijkstra跑出来是死循环，那么存不存在一个值，像spfa的单个点入队超过n次一样，能判断负环呢？我用一个裸的判断负环题做了个测试。

poj3259: 戳这里

测试代码如下：

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
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX_V = 200010;
const int MAX_E = 2000010;
const int INF = 0x3f3f3f3f;
int V,E,W,cnt;
int heap[MAX_V],dis[MAX_V];
int ans[MAX_V];
struct Edge{
    int to,next,cost;
}rng[MAX_E];
void add(int u,int v,int cost){
    rng[cnt].to = v;
    rng[cnt].next = heap[u];
    rng[cnt].cost = cost;
    heap[u] = cnt++;
}
struct Rule{
    bool operator()(int &a,int &b)const{
        return dis[a] > dis[b];
    }
};
inline int read()
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
bool Dijkstra(int a_){
    memset(dis,INF,sizeof(dis));
    priority_queue<int,vector<int>,Rule > q;
    dis[a_] = 0;q.push(a_);
    int loop = 0;
    while(!q.empty()){
        int u = q.top();q.pop();
        for(int k=heap[u];k != -1;k = rng[k].next){
            int &v = rng[k].to;
            if(dis[v] > dis[u] + rng[k].cost){
                dis[v] = dis[u] + rng[k].cost;
                q.push(v);
                ++loop;
              //  printf("%d\n", v);
                if(loop > V * E * V) return false;
            }
        }
    }
    return true;
}
int main(void){
    cnt = 0;


    int x,y,z;
    int t;
    t = read();
    while(t--)
    {
        memset(heap,-1,sizeof(heap));
        memset(ans, 0, sizeof(ans));
        V = read(),E = read(),W = read();
        for(int i=1;i<=E;i++){
        x = read(),y = read(),z = read();
        add(x,y,z);
        add(x, y, z);
        }
        for(int i = 1; i <= W; ++i)
        {
            x = read(), y = read(), z = read();
            add(x, y, -z);
       //     add(y, x, -z);
        }
        int flag = Dijkstra(1);
     //   printf("%d\n", dis[V]);
        if(flag)
            printf("NO\n");
        else
            puts("YES");
    }

    return 0;
}

我二分循环次数判断跳出，发现不是wa就是tle，看来这个时间复杂度很高。

可能是指数级的？

有大佬说是>n*Σ边权肯定ok (大雾

总之在这个猜想的过程中，对djkstra的实现大概有了新的认识，如果有感兴趣的朋友，可以继续研究研究。