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之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python实现Microsoft Office自动化的几种方式及对比详解

《Python实现MicrosoftOffice自动化的几种方式及对比详解》办公自动化是指利用现代化设备和技术,代替办公人员的部分手动或重复性业务活动,优质而高效地处理办公事务,实现对信息的高效利用... 目录一、基于COM接口的自动化(pywin32)二、独立文件操作库1. Word处理(python-d

JavaScript Array.from及其相关用法详解(示例演示)

《JavaScriptArray.from及其相关用法详解(示例演示)》Array.from方法是ES6引入的一个静态方法,用于从类数组对象或可迭代对象创建一个新的数组实例,本文将详细介绍Array... 目录一、Array.from 方法概述1. 方法介绍2. 示例演示二、结合实际场景的使用1. 初始化二

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

一文带你了解SpringBoot中启动参数的各种用法

《一文带你了解SpringBoot中启动参数的各种用法》在使用SpringBoot开发应用时,我们通常需要根据不同的环境或特定需求调整启动参数,那么,SpringBoot提供了哪些方式来配置这些启动参... 目录一、启动参数的常见传递方式二、通过命令行参数传递启动参数三、使用 application.pro

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑