首页 > 其他分享 >搜索与图论(二)-最短路问题(dijkstra、Bellman-Ford、SPFA、Floyd)

搜索与图论(二)-最短路问题(dijkstra、Bellman-Ford、SPFA、Floyd)

时间:2025-01-14 21:29:31浏览次数:3  
标签:dist idx int 算法 Bellman Ford SPFA 距离 include

目录

一、单源最短路问题 

1.朴素dijkstra算法O(n²)

 2.堆优化 Dijkstra 算法O(mlogn)

3.Bellman-Ford算法O(nm)

4.SPFA算法 O(m)/O(nm)

应用-判断负环

 二、多元最短路问题O(n³)

Floyd算法 


一、单源最短路问题 

问题定义:

1.朴素dijkstra算法O(n²)

适用于稠密图

  • 算法原理
    • 维护一个距离数组dist,用来记录从源点到各个顶点的最短距离,初始时,源点到自身的距离为 0,到其他顶点的距离为无穷大。
    • 还需要一个标记数组st,用于记录哪些顶点的最短距离已经确定。
    • 每次从尚未确定最短距离的顶点中,选择距离源点最近的顶点u,标记u的最短距离已确定。然后遍历u的所有邻接顶点v,如果通过u到达v的距离比当前记录的dist[v]更小,则更新dist[v]

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

const int N=510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++){ //迭代n次
        int t=-1;//t记录该轮确定的距离最短点
        for(int j=1;j<=n;j++){//从未确定最短距离点中找距离最小的点
            if(!st[j]&&(t==-1||dist[t]>dist[j])){
                t=j;
            }
        }
        st[t]=true;
        if(t==n) break;//优化
        //用这轮标记的点来更新未标记的点
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    int t=dijkstra();
    printf("%d\n",t);
    return 0;
}

 2.堆优化 Dijkstra 算法O(mlogn)

适用于稀疏图

  • 算法原理
    • 与朴素 Dijkstra 算法的不同在于,它使用堆(通常是优先队列)来优化寻找当前距离源点最近的未确定顶点的过程。
    • 优先队列中存储的是顶点以及从源点到该顶点的当前最短距离,每次从优先队列中取出距离最小的顶点,然后对其邻接顶点进行距离更新操作。如果更新后的距离更小,则将新的距离和顶点信息放入优先队列中。

由于该图顶点和边数目都多,用二维数组(邻接矩阵)存储空间占用大,故考虑用邻接表

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

typedef pair<int,int> PII;
const int N=150010;

int n,m;
//邻接表存储
int h[N],w[N],e[N],ne[N],idx;
int dist[N];//dist[i]表示结点1到结点n的距离
bool vis[N];//vis[i]表示结点i是否拓展过(该点最短距离固定)

void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof(dist));//初始距离为大数
    dist[1]=0;//初始化第一个结点到自己距离为0
    //最小堆,即按距离排序
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});//{距离,结点号}
    
    while(heap.size()){ 
        auto t=heap.top();//从堆中取距离最小的
        heap.pop();
        int ver=t.second,distance=t.first;
        if(vis[ver]) continue; 
        vis[ver]=true;//若没扩展,拿他进行扩展
        
        for(int i=h[ver];i!=-1;i=ne[i]){ //遍历其每一条边
            int j=e[i];
            if(dist[j]>distance+w[i]){
                dist[j]=distance+w[i];
                heap.push({dist[j],j}); //更新距离后放入堆中
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<dijkstra()<<endl;
    return 0;
}

3.Bellman-Ford算法O(nm)

Bellman-Ford算法以边为单位,进行n次迭代,每次迭代更新一遍每个点到起点的距离。Bellman-Ford算法对边的存储没什么要求,直接用一个类存储(C ++使用结构体)即可。

当题目规定只能经过k条边的最短路径时,只能用Bellman-Ford算法。

#include<iostream>
#include<cstring>
using namespace std;

const int N=510,M=10010;
int n,m,k;
int dist[N],backup[N];

struct Edge{
    int a,b,w;
}edges[M];

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){
        //备份距离数组,每次更新时应该用上一次迭代后的dist数组进行更新
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++){
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) puts("impossible"); //1压根到不了n,但有可能其它点(和1不连通+负权值)改变了到他的距离
    else printf("%d\n",dist[n]);
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    bellman_ford();
    return 0;
}

4.SPFA算法 O(m)/O(nm)

spfa算法是对Bellman-Ford算法的优化,Bellman-Ford每次都用当前点去更新其他点到起点的距离,如果当前点的距离没有变小的话,那么这个操作就是在浪费时间,所以spfa算法在此处进行了优化,利用一个队列,每当遍历到的点距离变小时,将其放入队列中,之后会用它去更新其他点的距离。

并且,spfa算法一般情况下很快,很多Dijkstra能做的spfa都能做,除了阴险的出题人编造数据时,将spfa算法时间复杂度卡成O(nm)的情况,spfa算法时间复杂度一般为O(m),最坏O(nm)。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

typedef pair<int,int> PII;
const int N=150010;

int n,m;
//邻接表存储
int h[N],w[N],e[N],ne[N],idx;
int dist[N];//dist[i]表示结点1到结点n的距离
bool st[N];//vis[i]表示结点i是否拓展过(该点最短距离固定)

void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

void spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) puts("impossible");
    else printf("%d\n",dist[n]);
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    return 0;
}

应用-判断负环

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

typedef pair<int,int> PII;
const int N=150010;

int n,m;
//邻接表存储
int h[N],w[N],e[N],ne[N],idx;
int dist[N],cnt[N];//dist[i]表示结点1到结点n的距离
bool st[N];//vis[i]表示结点i是否拓展过(该点最短距离固定)

void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

void spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    //注意开始时需要将所有点加入队列,要不然求的只是1号点能到的负环
    queue<int> q;
    for(int i=1;i<=n;i++) q.push(i);
    st[1]=true;
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n){
                    cout<<"Yes";
                    return;
                }
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    cout<<"No";
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    return 0;
}

 二、多元最短路问题O()

问题定义:

Floyd算法 

Floyd算法基于动态规划,使用三重循环,可以求解多源汇问题。由于Floyd算法是最短路算法的最后一个算法,所以在此进行总结。朴素Dijkstra常用于求解正权图中的稠密图,时间复杂度O(n²)、堆优化版Dijkstra常用于求解正权图中的稀疏图,时间复杂度O(mlogn)、Bellman-Ford算法常用于求解有边数限制的最短路问题,时间复杂度O(nm)、spfa算法常用于求解存在负权边的最短路问题(也可以求正权边最短路,有被卡风险)、Floyd算法常用于求解多源汇最短路问题,时间复杂度O(n³)。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

const int N=210,INF=1e9;
int n,m,Q;
int d[N][N];

void floyd(){
    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]);
}

int main(){
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;
        }
    }
    while(m--){
        int a,b,w;scanf("%d%d%d",&a,&b,&w);
        d[a][b]=min(d[a][b],w);//保留最短的重边
    }
    floyd();
    while(Q--){
        int a,b;scanf("%d%d",&a,&b);
        if(d[a][b]>INF/2) puts("impossible"); //因为有负权边
        else printf("%d\n",d[a][b]); 
    }
    return 0;
}

 

标签:dist,idx,int,算法,Bellman,Ford,SPFA,距离,include
From: https://blog.csdn.net/a2946501058/article/details/145145917

相关文章

  • 索引压缩算法 New PForDelta 简介以及使用 SIMD 技术的优化
     1.背景:搜索引擎与索引压缩 在搜索引擎或类似需要对海量文档进行检索的系统中,通常会构建倒排索引(InvertedIndex)。为降低存储成本、减少I/O并提升检索速度,对倒排索引所包含的大量整数序列进行压缩是一种行之有效的手段。•目标:在确保解压速度的同时,尽量获得更好的压缩......
  • Bellman-Ford\SPFA单源最短路算法
    Bellman-Ford单源最短路算法不采用SPFA实现的Bellman-Ford算法"题目中的图没有特殊性质时,若SPFA是标算的一部分,题目不应当给出Bellman–Ford算法无法通过的数据范围"Bellman-Ford的原理如下先枚举节点,在枚举边,每进行一轮循环,对图上所有的边都尝试进行一次松弛操作,当......
  • 代码随想录算法训练营第六十天|Bellman_ford队列优化法(SPFA)、bellman_ford之判断负
    前言打卡代码随想录算法训练营第49期第六十天(づ◕‿◕)づ首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的训练营大家庭一起进步。Bellman_ford队......
  • 代码随想录算法训练营第五十九天|dijkstra(堆优化版)精讲、Bellman_ford
    前言打卡代码随想录算法训练营第49期第五十九天⚆_⚆(˘❥˘)(•̀⌓•)シ(人•͈ᴗ•͈)♡♡首先十分推荐学算法的同学可以先了解一下代码随想录,可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解,卡哥清晰易懂的算法教学让我直接果断关注,也十分有缘和第49期的......
  • GPT 论文作者 Alec Radford 离开 OpenAI,曾参与开发 Whisper;闪极 AI 拍照眼镜支持全天
       开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(Real-TimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表......
  • 数据结构与算法学习笔记----SPFA算法
    数据结构与算法学习笔记----SPFA算法@@author:明月清了个风@@firstpublishtime:2024.12.19SPFA算法这同样是一种单源最短路径算法,是队列优化的Bellman-ford算法,因此他能处理的情况和Bellman-ford算法一样,但是在一般情况下,时间复杂度更低,为......
  • Bellman-ford算法
    有边数限制的最短路 #include<bits/stdc++.h>usingnamespacestd;constintN=510,M=10010,INF=0x3f3f3f3f;structEdge{inta,b,c;}edges[M];intn,m,k;intdist[N],last[N];//copy数组intbellman_ford(){memset(dist,0x3f,sizeofdist);dist[1......
  • 图论day64 :最短路径算法 | SPFA(Bellman_ford的队列优化版)、城市间货物运输 I、Ⅱ、Ⅲ
    图论day64:最短路径算法|SPFA(Bellman_ford的队列优化版)、94.城市间货物运输I(卡码网)【SPFA算法+邻接表优化】、95.城市间货物运输II(判断负权回路)、96.城市间货物运输III【已知有负权回路,该如何计算】、Bellman_ford算法思维导图汇总SPFA(Bellman_ford的队列优化版)94......
  • Stanford CS149 -- Assignment 4: NanoGPT149
    作业描述及代码参见:cs149gptWarm-Up:访问张量张量/数组都是按行存储的,四维数组可以看作元素为三维数组的数组,元素大小即为三维数组内元素总数,以此类推。第1部分:简单(但不太高效)的注意力机制实现主要实现两个矩阵乘法和一个softmax运算。第2部分:块矩阵乘法和UnfusedSof......
  • Stanford CS149 -- Assignment 1: Performance Analysis on a Quad-Core CPU
    作业描述及代码参加:CS149-asst1程序1生成view1时加速比与线程数的关系如下:线程数加速比22.0431.6942.5452.5763.2673.5584.11生成view2时加速比与线程数的关系如下:线程数加速比21.7532.2542.6753.146......