【算法学习笔记】22:SPFA算法(带负权边单源点最短路、检测负权回路)_spfa能解决含有负权回路的问题吗-程序员宅基地

技术标签: 检测负环  算法(学习)  单源点最短路  检测负权回路  负权边  SPFA  

1 简述

SPFA算法是对Bellman-Ford算法的优化,也是用于在存在负权边的图上,求单源点最短路,一般情况下时间复杂度可以看作 O ( m ) O(m) O(m)的,最坏情况下时间复杂度是 O ( n m ) O(nm) O(nm)

虽然SPFA算法是对Bellman-Ford算法的优化,但是不是所有用Bellman-Ford算法的问题都能用SPFA来代替。例如,对最短路经过的边数做一个限制,要求经过的边数 ≤ k \leq k k的最短路,这个时候能用Bellman-Ford算法,但是不能用SPFA算法来做。

SPFA算法是单源点最短路问题中限制最少的算法,在,单源点最短路的时候,只要图中没有负环就可以用SPFA算法,而且一般要求单源点最短路的问题都是没有负环的。只是如果没有负权边的话,用Dijkstra会更快,都是在有负权边的时候才用SPFA。


在Bellman-Ford算法中,循环 n n n次里,每次都要遍历所有的 m m m条边来做松弛操作更新 d i s t dist dist数组,但是实际上并不是每条边都能实际产生更新,SPFA就是对这个地方进行了优化。

观察
d i s t [ b ] = m i n ( d i s t [ b ] , l a s t [ a ] + w ) dist[b] = min(dist[b], last[a] + w) dist[b]=min(dist[b],last[a]+w)

可以发现,只有上一轮的 d i s t [ a ] dist[a] dist[a](也就是这一轮的 l a s t [ a ] last[a] last[a])变小了,这里的 l a s t [ a ] + w last[a] + w last[a]+w才会变小,才可能在这个式子里发生对 d i s t [ b ] dist[b] dist[b]的更新。而 b b b a a a的后继,只有前驱结点变小了后继结点才会发生更新

SPFA就是这样,用宽搜来做优化,维护一个队列,最开始先将起点(例如,是 1 1 1号点就加入 1 1 1)加到队列里去,作为更新的前驱。队列里存的始终是所有“变小了”的结点,所以只要队列不空,每次就应该取出队列里的所有结点,然后用这些结点出来的边来做更新,把这些边对应的后继结点全部放到队列里去。

这里如果用层序遍历的思想,则是要循环 n n n次,然后每次都把队列里所有的拿出来更新。但是实际上有更加自然的思想,就是不需要维护当前在第几层更新,而是只有更新成功的时候才把后继结点加入到队列里,这样只要队列空了那么所有的更新也就结束了。

这个过程写成伪代码如下:

将起点编号加入到队列里
while 队列不空
	取出队头t,注意pop出来
	更新t的所有出边,t-w->b,只有更新成功的时候,才把b加入到队列里

另外在加入队列之前可以再优化一下,如果队列里已经有 b b b了,就不用再加入了,因为在未来的某个时刻一定会把 b b b拿出来更新,这就足够了,不需要在意是因为结点 t 1 t_1 t1还是 t 2 t_2 t2的更新来导致了 b b b这个结点的变小,使 b b b的后继也要跟着更新。

2 应用:带负权边单源点最短路

模板题:spfa求最短路

注意SPFA相比Bellman-Ford算法的优化之后,每次是要拿出一个结点的所有后继边来尝试更新的,所以这个时候“结点后继”这个语义是需要的了,因此不能像Bellman-Ford算法那样直接把所有的边存到数组里去,这里直接存到邻接表里。

用STL的队列,不好判断一个结点是不是已经存在队列里了,这里的实现方式是用一个st数组来同步记录这个消息:如果一个结点t出队列了,就st[t] = false;如果一个结点b进入队列了,就st[b] = true

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = N;

// 带边权邻接表
int h[N], e[M], ne[M], idx, w[M];
void add_edge(int a, int b, int c) {
    
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++ ;
}

// 从源点1到每个结点的距离
// SPFA里不需要last数组,实际上SPFA的代码和Dijkstra的更像
int dist[N];
// st[j]记录结点j是否已经存在队列里,用于优化
bool st[N];

// SPFA算法求最短路,答案存在dist里
void spfa() {
    
    // 初始化dist数组
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 队列里保存更新了距离的结点,这些结点的后继要更新
    queue<int> q;
    q.push(1);
    // 注意st数组和队列要同步操作,后同
    st[1] = true;
    // 只要队列不空,就要一直更新
    while (q.size()) {
    
        // 取出队头元素t
        int t = q.front();
        q.pop();
        st[t] = false;
        // 对于t的所有后继b
        for (int i = h[t]; i != -1; i = ne[i]) {
    
            int b = e[i];
            // 如果能成功更新
            if (dist[b] > dist[t] + w[i]) {
    
                // 更新一下
                dist[b] = dist[t] + w[i];
                // 这个判断是优化,不判断而直接执行也行
                // 只要队列里没有,就加到队列里去
                if (!st[b]) {
    
                    q.push(b);
                    st[b] = true;
                }
            }
        }
    }
}

int main() {
    
    // 清空邻接表
    memset(h, -1, sizeof h);
    // 读取所有边
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
    
        int a, b, c;
        cin >> a >> b >> c;
        add_edge(a, b, c);
    }
    // 用SPFA跑一遍,dist数组里存的就是到每个点的最短路长度了
    spfa();
    // 这里也和B-F算法不一样
    // 由于SPFA从结点1开始确定地更新,不会出现inf更新其它结点的情况
    // 所以这里判断的时候直接写和inf做相等比较
    if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << dist[n] << endl;
    return 0;
}

3 应用:检测负权回路

模板题:spfa判断负环

如果有负权回路的话,求单源点最短路的过程就会一直下去,因为有负权回路的最短路可以一直越来越短。

由于SPFA里dist[j]记录了到j的最短距离,只要再维护一个cnt[j]表示到j经过了多少步就行了,所以如果经过了达到n步以上,这个路径上就一定有环,所以一定是负环。这和上一节学的用Bellman-Ford算法判断负环的思路是一样的。

写的时候大框架都是一样的,主要区别就是因为负环可以从任何一个点出发,所以初始的时候要把所有结点都加入到队列里。

另外在更新的时候,如果用 t t t更新 b b b更新成功了,那么到 b b b的距离 c n t [ b ] cnt[b] cnt[b]就应该更新成到 t t t的距离加上 1 1 1,也就是 c n t [ t ] + 1 cnt[t] + 1 cnt[t]+1

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = N;

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

int n, m;

int dist[N], cnt[N];
bool st[N];

bool spfa() {
    
    // 由于所有点都要入队,所以dist的语义已经不是单源点的最短路长度了
    // 而且求的不再是距离的绝对值,这里就默认全是0也一样能判断负环
    // memset(dist, 0x3f, sizeof dist);
    // dist[1] = 0;
    
    // 注意所有点出发都可能有负环,所以入队
    queue<int> q;
    for (int i = 1; i <= n; i ++ ) {
    
        q.push(i);
        st[i] = true;
    }
    
    while (q.size()) {
    
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
    
            int b = e[i];
            // 只要成功发生更新
            if (dist[b] > dist[t] + w[i]) {
    
                dist[b] = dist[t] + w[i];
                // 到b的距离就是到前驱t的距离再加1
                cnt[b] = cnt[t] + 1;
                // 立刻判断是不是达到n条边了,达到了就有环了
                if (cnt[b] >= n) return true;
                if (!st[b]) {
    
                    q.push(b);
                    st[b] = true;
                }
            }
        }
    }
    // 如果更新有尽头(才会到这),就一定没有环,也就没有负环
    return false;
}

int main() {
    
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
    
        int a, b, c;
        cin >> a >> b >> c;
        add_edge(a, b, c);
    }
    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

特别注意在这种求任意点出发的负环里,dist已经只是作为一个“比较和更新”的工具来用了,它的值是多少不关心,它的语义也不再是从单源点到某个点的最短路长度了。由于不关心距离的绝对值,所以也没必要初始化为正无穷,只要保证里面的数初始都是一样的,这样就能正常的根据w来更新就行了。

4 Java实现

模板题:spfa求最短路

import java.util.*;


public class Main {
    
    private static int n, m;

    private static int h[], e[], ne[], idx, w[];

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

    private static final int INF = (int) 1e9;
    private static boolean st[];
    private static int dist[];

    private static void spfa() {
    
        st = new boolean[n + 1];
        dist = new int[n + 1];
        for (int i = 1; i <= n; i++) dist[i] = INF;
        dist[1] = 0;

        Queue<Integer> q = new ArrayDeque<>();
        q.add(1);
        st[1] = true;
        while (q.size() != 0) {
    
            int t = q.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) {
    
                int j = e[i];
                if (dist[t] + w[i] < dist[j]) {
    
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
    
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        h = new int[n + 1];
        e = new int[m];
        ne = new int[m];
        w = new int[m];
        for (int i = 1; i <= n; i++) h[i] = -1;

        for (int i = 0; i < m; i++) {
    
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            ;
            int z = scanner.nextInt();
            add_edge(x, y, z);
        }

        spfa();

        if (dist[n] == INF) System.out.println("impossible");
        else System.out.println(dist[n]);
    }
}

模板题:spfa判断负环

import java.util.*;


public class Main {
    
    private static final int INF = (int) 1e9;
    static int n, m;

    static int h[], e[], ne[], idx, w[];

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

    static int[] dist, cnt;
    static boolean[] st;

    static boolean spfa() {
    
        dist = new int[n + 1];
        cnt = new int[n + 1];
        st = new boolean[n + 1];
//        for (int i = 1; i <= n; i++) dist[i] = INF;
//        dist[1] = 0;

        // 注意所有结点都要入队
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) q.add(i);

        while (q.size() > 0) {
    
            int t = q.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) {
    
                int j = e[i];
                if (dist[t] + w[i] < dist[j]) {
    
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if (cnt[j] == n) return true;
                    if (!st[j]) {
    
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        h = new int[n + 1];
        e = new int[m];
        ne = new int[m];
        w = new int[m];
        for (int i = 1; i <= n; i++) h[i] = -1;

        for (int i = 0; i < m; i++) {
    
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            add_edge(x, y, z);
        }

        if (spfa()) System.out.println("Yes");
        else System.out.println("No");
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/SHU15121856/article/details/113776859

智能推荐

【软件工具】之 TotalCommander_total commander-程序员宅基地

文章浏览阅读2.3w次,点赞3次,收藏57次。目录一、TotalCommander 简介二、TotalCommander 使用教程1、软件配置2、添加工具栏程序3、常用快捷键4、重新定义快捷键一、TotalCommander 简介Total Commander,简称 TC,原名 Windows Commander,功能强大的全能文件管理器。它支持随意自定义的菜单、工具栏、快捷键,给您最大的自由,打造个性TC,一般的文件操作,如搜索、复制、移动、改名、删除等功能应有尽有。功能介绍1、内置 ZIP/TAR/GZ/TGZ _total commander

入侵防御之snort安装_snort下载安装-程序员宅基地

文章浏览阅读2.6k次,点赞3次,收藏29次。snort的安装教程网上有很多,但是很多细节的小问题都没有呈现,前置库的安装大多也并不完全。如果刚开始实验的话可能会面临错误就像套娃一样产生的后果(我觉得这个套娃的比喻很恰当,甚至可以说是相当妙),而初装者往往不知道自己进行到了哪一步,可能面对这些错误又没法保持冷静和耐心。所以现将在kali中安装snort的过程及部分原因总结如下。着急的话可以直接跳到最后看具体代码。准备工作1.一些软件包可能会因为源的原因无法下载,而根据错误提示也很难定位具体原因,为了避免这种情况的发生,可以在安装snort前先_snort下载安装

lightoj 1233 - Coin Change (III) 多重背包+二进制优化-程序员宅基地

文章浏览阅读496次。n种硬币每种硬币有不同的面值,数量为c[i],问1-m里面有多少个价值可以被这些硬币组成...这个题范围似乎比上一道范围差不多但是时限给了2s...上一题的二进制优化多重背包跑了1.4s..这个题跑1.1s...单纯的二进制优化的多重背包,很裸...#includeusing namespace std;#define ll long long#define ull unsign_lightoj 1233

Java-7 连接mysql数据库的表数据(简单)_javamysql数据库连接到特定的表-程序员宅基地

文章浏览阅读354次。连接mysql数据库的表数据(简单)代码:import java.sql.*;public class Conn { //创建类Conn static Connection con; //声明Connection对象 static Statement sql; /..._javamysql数据库连接到特定的表

前端技术:vue(Vue项目中-axios设置默认请求地址和请求头)_vue在main中设置默认请求头后,更新header中请求头未更新-程序员宅基地

文章浏览阅读4.3k次。一、下载axios模块npm install axios --save二、在main.js中引用axiosimport axios from 'axios'三、设置默认请求地址axios.defaults.baseURL = 'http://localhost:8081/'; // 填写后台请求统一的地址四、设置默认请求头axios.defaults.headers['Cont..._vue在main中设置默认请求头后,更新header中请求头未更新

车牌识别及验证码识别的一般思路_codeformer 车牌识别-程序员宅基地

文章浏览阅读1.2k次。转自计算机视觉论坛:http://cvchina.net/forum.php?mod=viewthread&tid=1456&fromuid=2 本文源自我之前花了2天时间做的一个简单的车牌识别系统。那个项目,时间太紧,样本也有限,达不到对方要求的95%识别率(主要对于车牌来说,D,0,O,I,1等等太相似了。然后,汉字的识别难度也不小),因此未被对方接受。在此放出,同时描述一下思路及算法_codeformer 车牌识别

随便推点

安全防御 --- 防火墙_防火墙的安全防护机制-程序员宅基地

文章浏览阅读2.3k次,点赞2次,收藏9次。每个安全区域都有自己的优先级,用1-100的数字表示,数字越大,则代表该区域内的网络越可信。报文在两个安全区域之间流动时,我们规定:报文从低级别的安全区域向高级别的安全区域流动时为入方向(Inbound),报文从由高级别的安全区域向低级别的安全区域流动时为出方向(Outbound)。报文在两个方向上流动时,将会触发不同的安全检查。_防火墙的安全防护机制

机器学习算法——决策树算法(ID3算法划分数据集,基于香农熵的python底层实现)_采用id3算法解决二次分类数据集-程序员宅基地

文章浏览阅读1.7k次,点赞5次,收藏13次。决策树算法是一种非参数的决策算法,它根据数据的不同特征进行多层次的分类和判断,最终决策出所需要预测的结果。它既可以解决分类算法,也可以解决回归问题,具有很好的解释能力。决策树就如上图所示,决策树算法能够读取数据集合,构建类似于上图的决策树。决策树的一个重要任务是为了厘清数据中所蕴含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,在这些机器根据数据集创建规则时,就是机器学习的学习过程。传统的专家系统中经常使用决策树,而且决策树给出的结果往往可以匹敌在当前领域具有几十年工作经验的_采用id3算法解决二次分类数据集

学习-SpringCloudZuul gateway转发静态资源问题_springcloud gateway 静态资源-程序员宅基地

文章浏览阅读1.4w次。一、问题描述使用SpringBoot开发微服务应用时,使用Zuul开发API gateway,进行鉴权和验证,第一次配置路由之后,加载到页面发现没有获取静态资源文件,如下:zuul.routes.testweb.path=/page/**zuul.routes.testweb.url=http://localhost:8080/page二、解决方法此问题主要针对添加了类或项目映..._springcloud gateway 静态资源

Java面经(后台开发)校招准备资料汇总_后端开发校招咋么准备-程序员宅基地

文章浏览阅读5.5k次,点赞6次,收藏57次。一、刷题1.《剑指offer》---牛客 《剑指offer》面试题答案汇总(Java版)2.leetcode(个人觉得也是刷牛客上的这部分就够了)二、面经1.16年校招秋招笔试面试经验汇总2.还有一个很全的:Java研发方向如何准备BAT技术面试3.互联网公司校招Java面试题总结及答案——京东4.看准网和牛客都会有很多比较新的面经,可以自己去总结_后端开发校招咋么准备

Redis_redis bash-程序员宅基地

文章浏览阅读311次。初识Redisdocker ``exec` `-it docker-redis ``/bin/bashLinux安装Redis官网下载Redis解压Redis安装包 程序放到opt下面tar -zxvf 安装包进入解压后的文件安装基本的环境配置yum install gcc-c++makemake installredis 默认安装路径是usr/local/binredis默认不是后台启动;修改Redis配置文件启动Redis服务_redis bash

axios获取文件流,让iframe读取_iframe接受文档流-程序员宅基地

文章浏览阅读2.8k次。这里写自定义目录标题axios获取文件流,让iframe读取axios获取文件流,让iframe读取axios默认的返回类型是json数据,如果请求回来的数据不是json格式的,也会自动转成json格式,而有时候我们不希望它转成json格式的数据,这时就能通过改变responseType属性来把返回值设置成自己想要的格式,例如后台返回一个pdf文件流,用iframe请求的时候能直接通过src读取到,<iframe :src="url" width="100%" height="600px" &g_iframe接受文档流

推荐文章

热门文章

相关标签