最短路

Author Avatar
Axell 7月 25, 2019
  • 在其它设备中阅读本文章

边的存储

对于一般的无向图，可以按照有向图的方式添双向边

//边表存储，类似于链表
struct node{
    int Next,y,v;
}Pth[80005]; //注意无向图开双倍
int head[10005],cnt;
inline void add(int x,int y,int v){
    cnt++;
    Pth[cnt]={head[x],y,v};
    head[x]=cnt;
}

单源最短路

Dijkstra 算法

dijkstra算法可以求出图上的单源最短路，算法基于贪心的思想

在边权非负的图上，每次选取与源点最近的点（以前没选过的），扫描所有出边，更新每个终点到源点的距离

贪心思想的正确性：每次选出的结点一定不会被后选出的点更新（所有边权非负，当前不是最近的点无论怎么转移都不会比现在的近）

当然每次暴力找最近点的复杂度是n^2+m的，可以用堆优化成n log n + m

注意：Dijkstra 算法的贪心策略的正确性是基于边权非负的基础，因此必须保证边权非负才能跑，否则建议使用下面的SPFA算法

代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    int Next,y,v;
}Pth[500005];
int head[10005],cnt;
inline void add(int x,int y,int v){
    cnt++;
    Pth[cnt]={head[x],y,v};
    head[x]=cnt;
} 

int n,m,s,dis[10005];
bool v[10005];

void dij(){
    memset(dis,0x3f,sizeof dis); //初始化成最大值
    dis[s]=0; //dis[i]表示s->i的最短距离
    priority_queue <pair<int,int> > q;
    q.push(make_pair(0,s));
    while (!q.empty()){
        int x=q.top().second; q.pop();
        if (v[x]) continue;
        v[x]=1;
        for (int i=head[x];i;i=Pth[i].Next){
            int y=Pth[i].y;
            if (dis[y]>dis[x]+Pth[i].v){
                dis[y]=dis[x]+Pth[i].v;
                if (!v[y]) q.push(make_pair(-dis[y],y)); //相反数，把大根堆变成小根堆
            }
        }
    }
}

int main(){
    cin>>n>>m>>s;
    for (int i=1;i<=m;++i){
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        add(x,y,v);
    }
    dij();
    for (int i=1;i<=n;++i){
        if (dis[i]==0x3f3f3f3f){
            printf("2147483647 ");
        }else{
            printf("%d ",dis[i]);
        }
    }
    return 0;
}

Bellman-Ford算法

Bellman-Ford算法基于一个不等式，即d[x]<=d[y]+dist[y,x]，通过该不等式不断对d进行更新操作，直到不等式收敛，因此该算法可以在负权图上正常运行

复杂度为O(n*m)，一般是不符合题目限制的，因此有了SPFA

SPFA算法

SPFA即基于队列优化的Bellman-Ford算法，其基本思想是用一个队列保存待拓展的节点，每次从队头取出节点后，用所有出边更新，如果有节点被更新且不在队列中，则将该节点加入队列

复杂度一般为O(k*m)，k为较小的常数，但在特殊数据时复杂度最坏为O(n*m)，因此要谨慎使用

#include <bits/stdc++.h>
using namespace std;

struct node{
    int Next,y,v;
}Pth[500005];
int head[10005],cnt;
inline void add(int x,int y,int v){
    cnt++;
    Pth[cnt]={head[x],y,v};
    head[x]=cnt;
} 

int n,m,s,dis[10005];
bool used[10005];

void spfa(){
    memset(dis,0x3f,sizeof dis); //初始化成最大值
    dis[s]=0;
    queue <int> q; q.push(s);
    while (!q.empty()){
        int x=q.front(); q.pop();
        used[x]=0; //出队
        for (int i=head[x];i;i=Pth[i].Next){
            int y=Pth[i].y;
            if (dis[y]>dis[x]+Pth[i].v){
                dis[y]=dis[x]+Pth[i].v;
                if (!used[y]) q.push(y); //如果不在队列中则出队
            }
        }
    }
}

int main(){
    cin>>n>>m>>s;
    for (int i=1;i<=m;++i){
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        add(x,y,v);
    }
    spfa();
    for (int i=1;i<=n;++i){
        if (dis[i]==0x3f3f3f3f){
            printf("2147483647 ");
        }else{
            printf("%d ",dis[i]);
        }
    }
    return 0;
}

堆优化的SPFA算法

即将SPFA的队列改为优先队列，距离较小的优先拓展，复杂度很难给出，一般不会有数据卡（但洛谷上还是被卡了。。。）

关于负环

Bellman-Ford和普通的SPFA可以判负环

判定方法：

  1. Bellman-Ford 松弛n-1次后不等式仍未收敛，则有负环
  2. SPFA cnt[x]表示源点到x的最短路径包含的边数，更新时cnt[x]=cnt[y]+1,如果出现cnt[x]>=n，则有负环

多源最短路

Folyd算法

每次找一个松弛点，对其他任意点对进行松弛

枚举外层循环k，f[i][j]表示经过1-k个点时，i-j的最短路，复杂度为n^3

for (int k=1;k<=n;++k){
     for (int i=1;i<=n;++i){
         for (int j=1;j<=n;++j){
             d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
         }
     }
 }

folyd还可用于传递闭包，即如果i->j且j->k，则i->k

边权为0/1的单源最短路

一般用于二分答案的判定，用双端队列+BFS解决

  1. 双端队列中先只放源点
  2. 取出队头，扫描出边，计算终点的权值，如果该边权为1，则加入到队尾；反之加入到对头
  3. 一个节点第一次出队时即得到最短路，后续再出队时直接忽略

例题

LuoOJ 1828

在原图上求出1-x最小买入价A[x]，在反图中求出x-n最大卖出价B[x]，求出B[x]-A[x]最大值即可

if (dis[y]>min(dis[x],Pth[i].v)){
    dis[y]=min(dis[x],Pth[i].v);
    q.push(y); used[y]=1;
}

LuoOJ 2401

这题题目特性很重要，单向边有负权，双向边没负权，且单向边无环，先只添加双向边，划出连通块，然后添单向边，做拓扑排序，每次取出对头，对内部节点做dijstra

LuoOJ 2404

传递闭包即可，i>j即i->j，i<j即j->i，如果传递闭包完成后，每个i，j都有i>j或i<j则有解，否则无解或不确定

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/%E6%9C%80%E7%9F%AD%E8%B7%AF/