Day2

发表于 | 更新于: | 分类于 | | 阅读数

在要咕的边缘疯狂试探是时候补齐自己的图论知识了——Dijkstra算法和Floyd算法

首先这是一个对于无负权边的图的一个判别方法，如果有负权边那么就要使用另一个算法叫SPFA算法（先不深究）

Dijkstra算法

Dijlstra也就是单源最短路算法，能求出某个点到其他所有点的最短路

首先对于一个空集合，最少要进行$n$次操作，才能把所有点加入集合

然后对于每次加点，就要循环$n$次找出离集合最近的点，然后再次更新，dis数组

复杂度：$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Dijkstra(int x){//x是原点
    memset(dis,inf,sizeof dis); //先把dis赋值成一个巨大的数，为不可到达
    memset(vis,0,sizeof vis); //标记数组，vis[i]=0表示i不在集合里面
    vis[x]=1;  //初始集合只有x一个点
    for(int i=1; i<=n; i++) dis[i]=g[x][i]; //初始化，更新所有离x的点i的距离，放进dis数组
    for(int i=0; i<n; i++){ // 循环n次
        int mark=-1;
        int maxdis=inf;
        for(int j=1; j<=n; j++){
            if(!vis[j] && maxdis>dis[j]){ //找出未加入集合的点mark，这个mark点是集合外点中离x最近的
                maxdis=dis[j];
                mark=j;
            }
        }
        if(mark == -1) break;
        vis[mark]=1;  //加入集合
        for(int j=1; j<=n; j++){
            if(!vis[j])
                dis[j]=min(dis[j],dis[mark]+g[mark][j]); //再次更新dis数组
        }
    }
}

堆优化Dijkstra算法

万一$n$很大，上面的算法就会力不从心，我们用到c++的优先队列，priority_queue​

假定我们知道优先队列怎么用（cppreference），我们可以$logn$的找出集合外中哪个点的dis[i]最小，那么就把复杂度降低到$nlogn$，一般用上面足够了，下面还包含链式前向星的写法，可以学习一波哦

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
struct node{
    int val,id;
    node(int id,int val):id(id),val(val) {}
    bool operator <(const node &hs)const{
        return val>hs.val;
    }
};
struct edge{
    int next,to,w;
}e[maxm*2];
int head[maxn],cnt;

void addedge(int u,int v,int w){
    e[++cnt]=edge{head[u],v,w};
    head[u]=cnt;
}

int dis[maxn],vis[maxn];
void dijkstra(int from){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }
    priority_queue<node>q;
    q.push(node(from,0));
    dis[from]=0;
    while(!q.empty()){
        int cur=q.top().id;
        q.pop();
        if(vis[cur])continue;
        vis[cur]=true;
        for(int i=head[cur]; i ; i=e[i].next){
            int v=e[i].to;
            if(dis[cur]+e[i].w < dis[v]){
                dis[v]=dis[cur]+e[i].w;
                q.push(node(v,dis[v]));
            }
        }
    }
}

Floyd算法

单源最短路我们已经解决，如果问你每个点到每个点的最短路呢？就是说我要问任意一点的最短路，那么我们如果用Dijkstra算法，即使用了堆优化也需要$n^3logn$的时间复杂度，Floyd要好那么一点点，只要$n^3$（真的只是一点点）

Floyd的思想很简单，先枚举两个点 $i$ 、$j$点，我再枚举一个$k$点，那么$i$到$j$的最短路，要么通过$k$要么不通过，那么我们取最小值实现局部最优就能使总体最优，代码很简洁

1
2
3
4
5
6
7
for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }
}

总结

其实上面的算法都是贪心的思想，这是基于无负权边的前提下的，这点需要注意，这就是贪心思想的局限性，局部最优无法使整体最优。

thanks!