抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

图论：最短路相关算法- Dijstra，SPFA and Floyd

发布于：2023年7月15日

字数：2k 字

时长：9 分钟

Preface

暑假集训用到了最短路的板子但之前的板子没存下来，在加上之前也看的不是很明白，故这里放点笔记；

部分板子目前还未测试过，谨慎使用(2023.7.15)；

Content

Problem

用链式前向星方式存储一个有权图G(V:E)，找到点 i,j 之间权值最小的路径长度；

注意：有时题目中的图其实就是树，而树的路径长度用 dfs 就好了不需要用这个；

通常包括Dijstra 算法,SPFA 和 Floyd算法，其中小心SPFA被卡爆（）；

Solution

Dijstra 算法

Notice:

  • 该算法只能处理边正权图的单源最短路问题，但是它的效率十分优秀，一般采用带小根堆优先队列优化~~（ZKW线段树!Fibonnaci堆!）~~；

  • 时间复杂度为O((|V|+|E|)log|V|);

  • 但这个复杂度放在稠密图里可能会被hack,需要换成邻接矩阵的方式存图，复杂度为O(|V|^2),遇到了再补吧；

Proof：

  • 对于每个点v均维护一个「当前最短距离数组」dis[v] 以及「访问数组」vis[v] ,首先将dis[u]初始化为0，将其他点的距离初始化为无穷，并将所有点初始化为未访问的。记e[i]:u-v的边权为 e[i].w。然后进行以下步骤：
    1. 从所有未访问的点中，找出当前距离最小的,并将其标记为已访问的;
    2. 调整所有出边连接但尚未访问的点，转移状态；
    3. 重复1和2步骤，直到所有点都已访问，因为所有边权权值均为正的，所以用之后访问的结点是不能更新已经访问过的结点的（因为贪婪算法下若可以更新的话必定在还在之前就已经更新过了）；
    4. 可以用pre[y]=i维护最短的路径（点边关系）；

Template：

标准版询问单源最短路径

#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int N=200005;
struct Edge{
    int head;
    int to;
    int nxt;
    int w;
}e[N];
void add(int u,int v,int w,int& cnt,std::vector<int>& head){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u,e[cnt].to=v,e[cnt].w=w;
    cnt++;
    return ;
}//链式前向星建图
//*****************************************************************************************//

long long dis[maxn]; 
//int pre[maxn];
const int INF=1000000009;
class Node{//使用Node维护每次要更新的点和距离
public:
    long long distance;
    int position;
    Node(long long a,int b){distance=a;position=b;}
    bool operator >(const Node&obj) const{
        return distance>obj.distance;
    };
};
class cmp{//小根堆比较函数
public:
    bool operator()(Node&a,Node&b)const{
        return a>b;
    }
};
std::priority_queue<Node,std::vector<Node>,cmp> disQ;
void Dijstra(int u,int n,long long (&dis)[maxn],std::vector<int>& head/*,int (&pre)[maxn]*/){
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[u]=0;
    disQ.push(Node(0,u));//保存用来更新的队列
    bool vis[maxn];
    memset(vis,false,sizeof(vis));//初始化

    while(!disQ.empty()){
        int x=disQ.top().position;
        disQ.pop();
        if(vis[x]) continue; vis[x]=true;//不再对已访问过的位置进行访问
        for(int j=head[x];j!=-1;j=e[j].nxt){
            int y=e[j].to;//遍历当前位置的邻点，并更新它们
            if(dis[y]>dis[x]+e[j].w){
                dis[y]=dis[x]+e[j].w;
                if(!vis[y]) disQ.push(Node(dis[y],y))/*,pre[y]=i*/;
            }
        }
    }
    return ;
}
//****************************************************************************************//

int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m,s;
    std::cin>>n>>m>>s;

    int cnt=0;
    std::vector<int> head;//head[u],头为u的当前最晚出现的边标号
    head.resize(n+1,-1);
    for(int i=0;i<m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        add(u,v,w,cnt,head);
    }
    //memset(pre,0,sizeof(pre));
    Dijstra(s,n,dis,head);
    for(int i=1;i<=n;i++){
        if(i!=1) printf(" ");
        std::cout<<dis[i];
    }
    return 0;
}

Floyd 算法

Notice

  • 算法是基于最朴素的动态规划的思想，求出全局上的任意两点的最短路问题，可以处理负边权的情况；
  • 我们知道对于图G 中存在负权值环的话，沿着这个环一直前进是不会得到最短路的， 算法也无法处理这类的问题；
  • 在一些加了若干限制的最短路问题中，往往都要回归到朴素的算法来；

Proof

考虑对每个值，「到 的路径只允许经过标号不大于的点」中最短路径长度，明显是我们所求问题的答案；

  • 初始，所欲值都是正无穷；

  • 递归的说，对于已有的允许的最短路径，新的最短路径要么经过,要么维持不变；

  • 状态转移方程为

  • 时间复杂度为;

Template:

弱化版单源最短路径，不是正解，只有70分

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
const int maxn=10005;
const int N=500005;

long long dis[maxn][maxn]; 
const long long INF= (1<<31)-1;
void Floyd(int n,long long (&dis)[maxn][maxn]){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m,s;
    std::cin>>n>>m>>s;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]= INF;
        }
    }
    for(int i=0;i<m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        dis[u][v]=std::min(dis[u][v],w*1LL);//可能由重边
    }
    
    Floyd(n,dis);
    for(int i=1;i<=n;i++){
        if(i!=1) printf(" ");
        std::cout<<((i!=s)?dis[s][i]:0);
    }
    return 0;
}

SPFA 算法

Notice:

  • 对于一般的带权图，不同于正权图的操作每次取出最小的来进行下一步，边权有负数是不保证正确性的，所以我们维护一个普通的队列就行了，这也是经常得卡爆的地方，构造数据可以欺骗算法进入冗余的分支，使得队列的进出和多了很多不必要的操作；
  • 这个算法本质是算法的局部优化，复杂度为；
  • 所以说没必要仔细解释算法对全局的次操作了，卡的一定卡;
  • （保证输入是随机数据）慎用，不要偷懒！因为它已经死了；

Template:

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
const int maxn=100005;

const int N=500005;
struct Edge{
    int head;
    int to;
    int nxt;
    int w;
}e[N];
void add(int u,int v,int w,int& cnt,std::vector<int>& head){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u,e[cnt].to=v,e[cnt].w=w;
    cnt++;
    return ;
}
//******************************************************************************//
const long long INF=(1<<31)-1;
long long dis[maxn];
void SPFA(int s,int n,long long (&dis)[maxn],std::vector<int> &head){
    for(int i=1;i<=n;i++) dis[i]=INF;
    dis[s]=0;
    bool vis[maxn];
    memset(vis,false,sizeof(vis));

    std::queue<int> disQ;
    disQ.push(s);
    while(!disQ.empty()){
        int x=disQ.front();
        disQ.pop();
        vis[x]=false;
        for(int i=head[x];i!=-1;i=e[i].nxt){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].w){
                dis[y]=dis[x]+e[i].w;
                if(!vis[y]){
                    vis[y]=true;
                    disQ.push(y);
                }
            }
        }
    }
}
//*************************************************************************************//
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m,s;
    std::cin>>n>>m>>s;

    int cnt=0;
    std::vector<int> head;//head[u],头为u的当前最晚出现的边标号
    head.resize(n+1,-1);
    for(int i=0;i<m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        add(u,v,w,cnt,head);
    }
    //memset(pre,0,sizeof(pre));
    SPFA(s,n,dis,head);
    for(int i=1;i<=n;i++){
        if(i!=1) printf(" ");
        std::cout<<dis[i];
    }
    return 0;
}

Example

暂时没有；

洛谷P3385 【模板】负环

洛谷P5909【模板】Johnson 全源最短路

Remark

已寄，这篇就当笔记吧；

更新于：2023年11月7日

图论

算法

评论




博客内容遵循 [署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh)
本站使用 Volantis 作为主题
[Copyright © since 2023. All rights reserved](/)
字数统计：15.7k
<