自己做网站教学视频教程,wordpress免费用户,网站验证图标,正能量软件不良网站直播算法核心代码实现负权环判断负权环 根据松弛次数根据最短路径上的死循环 SPFA#xff08;Shortest Path Faster Algorithm#xff09;#xff08;队列优化#xff09;算法是求单源最短路径的一种算法。它是在Bellman-ford算法的基础上加上一个队列优化#xff0c;减少了冗… 算法核心代码实现负权环判断负权环 根据松弛次数根据最短路径上的死循环 SPFAShortest Path Faster Algorithm队列优化算法是求单源最短路径的一种算法。它是在Bellman-ford算法的基础上加上一个队列优化减少了冗余的松弛操作是一种高效的最短路算法。 Bellman-Ford算法虽然可以处理负环但是时间复杂度为O(ne)e为图的边数在图为稠密图的时候是不可接受的。 Bellman-Ford算法的缺点在于当某一个迭代求解已经获得了所有的最短路径后它还是会继续执行没有执行完的迭代求解。但其实不用这样。 分析不难发现起点s到某一个点的最短路径的第一条边必定是s与s的邻接点连成的边。所以当我们在第一次松弛即第一次迭代求解时时松弛的边必定包含最短路径的第一条边。 而最短路径的第二条边必定是s的邻接点与s的邻接点的邻接点连成的边。这样以此类推。
算法核心
因此可以对算法进行优化。设置一个队列初始的时候将s放入队列中。 【1】队列出队出队元素为current松弛current与其邻接点相连的边将松弛成功的邻接点放入队列中这些点中包含其最短路径的第二个点第一个点为起点 【2】然后再次队列出队出队元素为current松弛current与其邻接点相连的边但如果已在队列中就不要重复入队了 【3】重复以上步骤 其实这个步骤和无权最短路径算法有点像。
代码实现 from queue import Queue
class Edge():def __init__(self,u,v,cost):self.u uself.v vself.cost cost
nodenum 5edgeList []
dis [float(inf)]*nodenum
pre [-1]*nodenum
know [False]*nodenum#代表已在队列之中edgeList.append(Edge(1,4,2))
edgeList.append(Edge(0,2,4))
edgeList.append(Edge(3,2,5))
edgeList.append(Edge(3,1,1))
edgeList.append(Edge(1,3,2))
edgeList.append(Edge(4,3,-3))
edgeList.append(Edge(0,1,-1))
edgeList.append(Edge(1,2,3))edgenum len(edgeList)original 0
def SPFA(original):q Queue()dis[original] 0know[original] Trueq.put(original)while(not q.empty()):current q.get()know[current] False#循环遍历current的邻接顶点for edge in edgeList:if(edge.u current):#current点的邻接边temp dis[edge.u] edge.costif(temp dis[edge.v]):#松弛操作dis[edge.v] temppre[edge.v] currentif(not know[edge.v]):q.put(edge.v)know[edge.v] Trueprint(当前出队的元素为,current)print(dis)print(pre,\n)SPFA(original)
print(\n,dis)
print(pre) 从运行结果可以看出程序的执行过程。2出队了两次说明它也入队了两次。从上到下观察dis数组可以发现每个点的dis最多被更新两次有的更新一次就更好好了。
负权环
当图中有负权环时队列就不会有空的情况了因为由于负权环的存在负权环上的点就可以一直被松弛一直能被松弛就代表着队列会不断反复让负权环上的点入队出队程序就会死循环。 修改边的权重为
edgeList.append(Edge(0,1,-1))
edgeList.append(Edge(1,2,3))
edgeList.append(Edge(3,1,1))
edgeList.append(Edge(1,3,2))
edgeList.append(Edge(1,4,2))
edgeList.append(Edge(0,2,4))
#edgeList.append(Edge(3,2,5))
edgeList.append(Edge(2,3,-5))
edgeList.append(Edge(4,3,-3)) 如图所示形成了123的负权环。 此时运行结果会无限输出不停有元素出队入队所以程序陷入了死循环。
判断负权环
根据松弛次数
n代表节点个数。 根据松弛次数是否大于等于n来判断负权环是从网上其他博客说的根据出队次数是否大于等于n来判断想到的。因为判断出队次数是判断更新次数的上界。 用一个n大小的数组来代表每个点的松弛次数。因为SPFA算法里的松弛和Bellman-ford算法里的松弛一样。Bellman-ford算法里对同一个点的松弛次数在极端情况下可以想象把这些松弛次数分配到每一次迭代求解中去而迭代求解一共只有n-1次。所以一旦某个点的松弛次数等于了n那么就说明有负环。 所以在每次进行松弛后遍历判断每个点的松弛次数如果有一个等于n再执行下去就会大于n就说明有负环。
#用松弛次数来判断负权环
from queue import Queue
class Edge():def __init__(self,u,v,cost):self.u uself.v vself.cost cost
nodenum 5edgeList []
dis [float(inf)]*nodenum
pre [-1]*nodenum
know [False]*nodenum#代表已在队列之中update [0]*nodenum#代表每个点被更新的次数edgeList.append(Edge(0,1,-1))
edgeList.append(Edge(1,2,3))
edgeList.append(Edge(3,1,1))
edgeList.append(Edge(1,3,2))
edgeList.append(Edge(1,4,2))
edgeList.append(Edge(0,2,4))
#edgeList.append(Edge(3,2,5))
edgeList.append(Edge(2,3,-5))
edgeList.append(Edge(4,3,-3))edgenum len(edgeList)original 0
def SPFA(original):q Queue()dis[original] 0know[original] Trueq.put(original)while(not q.empty()):current q.get()know[current] Falseflag False#负环判断标记#循环遍历current的邻接顶点for edge in edgeList:if(edge.u current):#current点的邻接边temp dis[edge.u] edge.costif(temp dis[edge.v]):#松弛操作dis[edge.v] temppre[edge.v] currentupdate[edge.v] 1for i in update:if(inodenum):flag Trueprint(最后一次出队的是,current)breakif(flag True):breakif(not know[edge.v]):q.put(edge.v)know[edge.v] Trueif(flag True):breakprint(当前出队的元素为,current)print(dis)print(pre,\n)SPFA(original)
print(dis,dis)
print(pre,pre)
print(update,update) 运行结果并没有全部截图下来因为中间执行了很多次不该有的出队入队操作每次出队都输出东西这里只截了最后结果。可以看到update数组中有一个等于了5所以程序就判断有了负权环。 而且读者可以通过所有的输出结果统计每个点出队次数会发现这些点里面出队次数最大也就为4我用画正字来记的数。意思就是如果程序通过出队次数来判断的话那么程序还得多执行几次不该有的出队入队操作。这也证实了判断出队次数是判断更新次数的上界。 但通过所有输出结果还是觉得程序判断出负权环判断得太迟了中间执行了很多次不该有的出队入队操作有没有一种更快的方法可以及早判断出负权环呢。答案是有如下。
根据最短路径上的死循环
寻找最短路径的方法是通过pre数组 比如代码实现章节的程序运行后pre数组为[-1, 0, 1, 4, 1]要寻找从起点0到3的最短路径步骤如下 【1】记录下3路径为3 【2】记录下pre[3]4路径为43 【3】记录下pre[4]1路径为143 【4】记录下pre[1]0路径为0143 【4】记录下pre[0]-1遇到-1到达终点返回路径0143 从起点到某点的最短路径路径上的点必定都是不重复的。但当有负权环时这句话就不成立了。 比如负权环章节的程序运行后pre数组为[-1, 3, 1, 2, 1]寻找从起点0到3的最短路径会发现上述步骤会一种进行下去因为到达不了终点死循环了虽然这里程序是用的递归。
#此程序用pre数组的死循环来判断是否有负环
from queue import Queue
class Edge():def __init__(self,u,v,cost):self.u uself.v vself.cost cost
nodenum 5edgeList []
dis [float(inf)]*nodenum
pre [-1]*nodenum
know [False]*nodenum#代表已在队列之中edgeList.append(Edge(0,1,-1))
edgeList.append(Edge(1,2,3))
edgeList.append(Edge(3,1,1))
edgeList.append(Edge(1,3,2))
edgeList.append(Edge(1,4,2))
edgeList.append(Edge(0,2,4))
#edgeList.append(Edge(3,2,5))
edgeList.append(Edge(2,3,-5))
edgeList.append(Edge(4,3,-3))edgenum len(edgeList)original 0def if_circle(pre):#判断是否有负权环返回真假如有负权环并返回环prev -1#设置环的起点circle []#记录负权环def get(i):circle.append(i)if(i -1):#到达了正常的终点判断无负权环return Falseif(i prev):#到达了不该达到的终点判断有负权环return Truereturn get(pre[i])for i in pre:if(i -1):#超出索引限制了continueprev iif(get(pre[i])):#传入参数直接是i的上一个顶点直接传入i会出错return (True,circle)circle.clear()return (False,)def SPFA(original):q Queue()dis[original] 0know[original] Trueq.put(original)while(not q.empty()):current q.get()know[current] Falseflag False#循环遍历current的邻接顶点for edge in edgeList:if(edge.u current):#current点的邻接边temp dis[edge.u] edge.costif(temp dis[edge.v]):#松弛操作dis[edge.v] temppre[edge.v] currentif(if_circle(pre)[0]):print(有负环为,if_circle(pre)[1])print(dis)print(pre)flag Truebreakif(not know[edge.v]):q.put(edge.v)know[edge.v] Trueif(flag True):breakprint(当前出队的元素为,current)print(dis)print(pre,\n)SPFA(original)
print(\n,dis)
print(pre) 通过这种方式程序可以很快地判断出来负权环程序只出队了4次就判断出来了。且得到了负权环的组成的点[2, 1, 3]。
