BFS、SPFA、Dijkstra算法中vis数组的用法对比

2024-01-05 22:44

本文主要是介绍BFS、SPFA、Dijkstra算法中vis数组的用法对比,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

先上代码:

BFS:

bool vis[MAXN];
int dis[MAXN];void bfs(int s)
{queue<int> Q;Q.push(s);vis[s] = true;while(!Q.empty()){int u = Q.front();Q.pop();for(int e = first[u]; e; e = nxt[e]){int v = go[e];if(vis[v]) continue;dis[v] = dis[u] + 1;vis[v] = true;Q.push(v);}}
}

SPFA:

int dis[MAXN];
bool vis[MAXN];void SPFA(int s)
{for(int i = 1; i <= n; ++i) dis[i] = inf;dis[s] = 0;queue<int> Q;Q.push(s);vis[s] = true;while(!Q.empty()){int u = Q.front();Q.pop();vis[u] = false;for(int e = first[u]; e; e = nxt[e]){int v = go[e];if(dis[v] > dis[u] + val[e]){dis[v] = dis[u] + val[e];if(!vis[v]){Q.push(v);vis[v] = true;}}}}
}

Dijkstra:

struct node
{int u, ds;friend bool operator<(const node& n1, const node& n2){return n1.ds > n2.ds;}
};bool vis[MAXN];
int dis[MAXN];void Dijkstra(int s)
{memset(dis, 0x3f, sizeof(dis));dis[s] = 0;priority_queue<node> Q;Q.push({s, 0});while(!Q.empty()){int u = Q.top().u;Q.pop();if(vis[u]) continue;vis[u] = true;for(int e = first[u]; e; e = nxt[e]){int v = go[e];if(dis[v] > dis[u] + val[e]){dis[v] = dis[u] + val[e];if(!vis[v]) Q.push({v, dis[v]});}}}
}

分析对比

在BFS算法中

当Q.push()调用时顺便设置vis数组。原因是,BFS只能应用于边权为1的有向无环图(Directed Acyclic Graph, DAG),节点v第一次被搜索到时的dis值就是s→v的最短路。因此,在后面又访问到v时,根本不需要干任何事情,既不需要加入队列,也不需要更新dis值。因此,vis数组确保每个点只入队一次、dis值只被更新一次。

在SPFA(队列优化的Bellman-Ford算法)中

vis数组标记了节点v是否在Q中。元素出队时vis设置为false,入队时设置为true。如果节点v已经在队列中,则不需要再次入队。SPFA可以看作时BFS的衍生算法,它可以用于任意图,包括多重图、含有自环的图。对于已经访问过的节点,如果形成环路,后面的节点可以更新前面节点的dis值。其实可以去掉vis数组,但是这样会导致某一时刻队列中包含多个同一元素,极大地降低了算法的效率。因为同一时刻队列中有多个同一元素和只有一个该元素的效果是一样的。

Dijkstra算法是一个较为复杂的算法。根据《算法导论》

Dijkstra算法在运行过程中维持的关键信息是一组结点集合S。从源结点s到该集合中每个结点之间的最短路径已经被找到。算法重复从结点集V-S中选择最短路径估计最小的结点u,将u加入到集合S,然后对所有从u出发的边进行松弛。(P383)
算法维持的不变式为Q=V-S。(P384)(注:V是所有结点的集合,Q是优先队列,S为已经求出最短路的结点集合)
Dijkstra的暴力算法会维持该循环不变式。但我们的算法并不会,因为只有被松驰过的结点才有可能加入队列。理由是,没有被松驰过的结点其dis值一定是inf。Dijkstra还满足一个定理
定理 队列Q中dis值最小的结点u,其dis值就是s→u的最短路。
因此,我们的vis数组的意义是标志结点u是否属于集合S,即结点u的最短路是否已经被计算出来。当u出队时,根据定理,其最短路一定已经被计算出来了,因此标记vis[u]=true。在这之前,我们写道:
if(vis[u]) continue;
不加这句话会TLE。原因何在?为什么同一个结点会出队两次?因为它可能入队两次。或者说,它出队之前被连续松弛了超过一次,导致它在队里有好几个。因此我们使用vis数组,保证不走冤枉路。(亲测,if(!vis[v]) Q.push({v, dis[v]})中if(!vis[v])可以去掉)
区别Dijkstra和SPFA的一个方法是:Dijkstra末有4个右花括号,SPFA有5个

这篇关于BFS、SPFA、Dijkstra算法中vis数组的用法对比的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/574393

相关文章

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模

mysql中的group by高级用法

《mysql中的groupby高级用法》MySQL中的GROUPBY是数据聚合分析的核心功能,主要用于将结果集按指定列分组,并结合聚合函数进行统计计算,下面给大家介绍mysql中的groupby用法... 目录一、基本语法与核心功能二、基础用法示例1. 单列分组统计2. 多列组合分组3. 与WHERE结合使

Java中Scanner的用法示例小结

《Java中Scanner的用法示例小结》有时候我们在编写代码的时候可能会使用输入和输出,那Java也有自己的输入和输出,今天我们来探究一下,对JavaScanner用法相关知识感兴趣的朋友一起看看吧... 目录前言一 输出二 输入Scanner的使用多组输入三 综合练习:猜数字游戏猜数字前言有时候我们在

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

Linux命令之firewalld的用法

《Linux命令之firewalld的用法》:本文主要介绍Linux命令之firewalld的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux命令之firewalld1、程序包2、启动firewalld3、配置文件4、firewalld规则定义的九大

SQL BETWEEN 的常见用法小结

《SQLBETWEEN的常见用法小结》BETWEEN操作符是SQL中非常有用的工具,它允许你快速选取某个范围内的值,本文给大家介绍SQLBETWEEN的常见用法,感兴趣的朋友一起看看吧... 在SQL中,BETWEEN是一个操作符,用于选取介于两个值之间的数据。它包含这两个边界值。BETWEEN操作符常用

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程