村级网站建设 不断增强,常州哪些网站公司做的好处,wordpress邮箱发文,利用ps做兼职的网站这里写目录标题 xmind单源最短路简介所有边权都是正朴素的Dijkstra算法思想例子题解 堆优化版的Dijkstra算法 存在负数权Bellman-Ford算法思想例子题解 spfa算法思想例子题解 spfa判断负环思想例子题解 多源汇最短路简介弗洛伊德算法思想例子题解 小tips xmind 上述中#xff… 这里写目录标题 xmind单源最短路简介所有边权都是正朴素的Dijkstra算法思想例子题解 堆优化版的Dijkstra算法 存在负数权Bellman-Ford算法思想例子题解 spfa算法思想例子题解 spfa判断负环思想例子题解 多源汇最短路简介弗洛伊德算法思想例子题解 小tips xmind 上述中朴素Dijkstra算法适用于稠密图 其他用堆优化版
而SPFA算法一般都比Bellman-Ford算法要快
Floyd没得选
稠密图和稀疏图的定义 其中m是边数n是点数 当m的数据量与n方一样或者更多那么就是稠密图如果m跟n数据量一样或者说更少那么就是稀疏图 最短路问题只会考察如何抽象出问题并实现代码并不会考察算法的原理重点在于抽象以及代码的实现
单源最短路
简介
只有一个起点到其他某个点的最短路
所有边权都是正
朴素的Dijkstra算法
思想 一些解释 s数组存放目前已经确定的最短距离的点 第一步中dis数组是某个点到原点的距离初始化一号点一号点就是源点因为图论中结点的编号都是从1开始的的dis数值为0其他全为一个很大的数 第二步中for 遍历i从0到n 对于每次循环 将不在s中的距离dis最近的点给到t 把t加到s 用t来更新其他所有点的距离如上图如果满足dis[x]dis[t]w(t到x的权值)那么更新dis[x]的值为dis[t]w的值
因为该算法适用于稠密图所以用邻接矩阵来存储图
例子题解
手动过滤自环和重边 数据分析n m分别是点数和边数 g数组存放某两个点的权值例如g[a][b]1,表示a与b之间的权值是1 dist数组用来存放某个点到原点也就是一号点的距离 st数组就是用来表示某个点的最短路已经被找到
dijkstra算法 首先初始化dist为无穷大用十六进制0x3f初始化即可 之后初始化dist[1]为0因为一号点是源点
之后for循环循环n次 首先初始化t为-1 之后对于每个节点编号从1到n if(某个点没有确定最短路并且(t未被赋值或者j是没有确定最短路的最近的点即dist[t]dist[j]) )这时将j赋值给t 同时更新st[t]为true 然后对每个节点编号进行循环用t更新其他结点的最短路 dist[j]min(dist[j],dist[t]g[t][j]) 最后如果dist某个点的距离仍然是0x3f因为利用memset初始化是初始其值的四分之一即可但是0-1是初始化自己那么返回-1表示路径不存在 最后返回dist[n],这里根据具体的题目要求进行返回即可因为题目让返回n号点 之所以取min是因为该题存在自环和重边如下但是因为要求最短路所以当某两个点有多个权值的时候取权值最小的当做其权值较大的权值就不看了
堆优化版的Dijkstra算法
无需手动过滤自环和重边算法自己过滤 题目与上面的题一样 对于add算法 idx表示当前e数组中的可用位置将目标点的编号存入e[]数组中并且用一个w数组来维护权值同时头插法ne[idx]h[a],h[a]idx 因为e数组就是用来存节点信息的又因为e数组所存信息的结点都是一个节点的出边节点组成的链表所以信息就是节点的编号所以目标结点的编号都放在e[]数组里发出结点的编号都在h数组所以函数里都是h[a] 要明确这里所说的图中的结点只有结点编号以及某两个点的权值没有具体的意义数字比如一号点表示着某些意义这是不存在的如果有意义数组那么极有可能没给编号那么可以将意义数字当成编号处理 首先是一个优先队列其中第二第三个参数是用来改变默认排序改成从大到小排列 用一个pari来维护一个结点编号以及该点到源点的距离
while循环条件队列不空 然后取出队头元素给到t没有确定最短路径的点且距离源点最近 之后将队头元素出队 然后拿到t的编号以及到源点的距离 if(st[ver]是真)那么说明这是重边countinue即可 之后用t来更新其他结点的最短路径: for循环中遍历t结点的所有一级出边对于每个子链结点拿到其存在e数组中的编号之后给j 之后更新 之后出队j的pair{dist[j],j} 存在负数权
Bellman-Ford算法
思想 上面的方框是算法过程下面的圆是经过该算法之后出现的现象即对于每个abdist[b]dist[a]w俗称三角不等式 其中 第一个for循环的次数是有实际意义的循环k次表示最短路径最多经过不超过k条边到达目标点 例子题解
无需手动过滤自环和重边算法自己过滤 输出案例3 数据分析 backup数组是用来备份dist数组的 结构体用来存放某两个点以及两个点之间的距离 并用该结构体类型创建边数组
对于bellman-ford算法 首先初始化dist数组 之后因为题目要求最多不超过k条边所以循环k次 在k次循环的每次循环时首先备份dist到backup数组 然后对于m条边有m次循环因为结构体来存放边每个边是一个结构体元素所以有几个边就循环几次 之后利用结构体数组拿到每个边的数据利用备份的a来更新dist[b] 最后如果n点具体哪个点看题目要求的dist0x3f3f3f/2记住就好那么就表示没有最短路径 最后返回dist[n]
对于为什么要备份如下 因为有k条边的限制所以不能向之前那样一个接着一个更新这样的话就会无视k条边的限制直接找到没有限制的最短路径 利用备份的数据进行更新每次都是最初版本的数据都是正无穷所以不会发生数据更新就会被限制到
spfa算法
思想
适用于没有负权回路 spfa算法是对Dijkstra算法的优化优化的是上面打勾的那一步的处理
之前Dijkstra算法对于更新dist[b]的思路是不管三七二十一遍历寻找t去更新dist[b] 这里spfa对dist[a]或者说t对其进行判断是否被更新如果被更新了才能去更新别的点同时队列里只存放已经被更新的结点拿着队列中已经被更新的点去更新其他点才能有效
例子题解
无需手动过滤自环和重边算法自己过滤 spfa算法与Dijkstra算法差不多唯一不同的是函数是Dijkstra函数改成spfa函数 数据分析nm仍然是n个点m条边 之后h数组w数组e数组ne数组idx都是用来构建邻接表 dist表示某个点到原点的距离 而这里不同于Dijkstra算法st数组表示某号结点是否在队列中例如st[2]表示二号点已经在队列中 spfa算法 首先初始化dist并初始化dist[1]0
然后定义一个队列元素为int 该队列用来存放那些已经被更新的结点哪些编号的点已经被更新 一号已经更新入队
之后while队列不空{ 取出队头元素编号用t接住 之后队头出队 将t编号的状态改为false因为t已经出队了 之后遍历t的所有子链即所有一级出边节点通过e数组拿到编号 之后看能否用t进行更新如果可以则更新同时判断j点是否在队列不在的话就入队并将st数组改为true }
最后有返回值根据具体情况来定如下图
spfa判断负环
思想 我们在更新dist数组时维护一个cnt数组表示从某个点到源点的最短路上一共有多少条边 每次更新dist时说明有更新更新的是从源点到t之后再加上从t到x那么就是cnt[t]1
一旦发现cnt[x]n因为正常情况下应该是小于n的那么一定存在一个负环使得多出了一些边所以cnt[x]n表示存在负环
例子题解
无需手动过滤自环和重边算法自己过滤 如下是利用spfa算法判断负环的整体算法他是在spfa算法上做了一些修改如下标注 数据方面多一个维护数组cnt[N] 之后在spfa函数中首先while循环里那个虚框可以忽视画错了 在while循环里 在dist更新代码下面更新一下cnt[j]cnt[t]1; 同时判断如果cnt[j]n,那么返回true表示有负环 如果最后没有返回true那么在最后返回false
“spfa函数里”到“while循环上面”的代码整体修改为下图因为题目要求求所有的负环而不是以1为源点的负环所以将所有点都放入队列 多源汇最短路
简介
多个起点
弗洛伊德算法
思想 弗洛伊德算法是用邻接矩阵来存g[i][j]表示从i点到j点的权值或者没有权值有边就是1没边就是0
例子题解
手动过滤自环和重边 数据分析INF宏定义为1e9表示无穷大 floyd函数三重循环 从k从1到n i从1到n j从1到n 并更新邻接矩阵 main函数里第一个二重循环是在处理自环将自环初始化为0其余初始化为INF 之后的while循环里是在初始重边有重边时取最小的 之后调用floyd函数 第二个while函数是在处理输出这里注意ifdINF / 2那么表示没有最短路
小tips
数据量在某个时间复杂度的计算下小于一千万表示一秒之内可以出解
