SPFA算法详解——判断负权环

你的名字 2022-05-21 13:10 336阅读 0赞

*  算法核心
 *  代码实现
 *  负权环
 *  判断负权环
    
     *  根据松弛次数
     *  根据最短路径上的死循环

SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法。它是在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。  
[Bellman-Ford算法][Bellman-Ford]虽然可以处理负环，但是时间复杂度为O(ne)，e为图的边数，在图为稠密图的时候，是不可接受的。  
Bellman-Ford算法的缺点在于，当某一个迭代求解已经获得了所有的最短路径后，它还是会继续执行没有执行完的迭代求解。但其实不用这样。  
分析不难发现，起点s到某一个点的最短路径的第一条边，必定是s与s的邻接点连成的边。所以当我们在第一次松弛（即第一次迭代求解时）时，松弛的边必定包含最短路径的第一条边。  
而最短路径的第二条边，必定是s的邻接点与s的邻接点的邻接点连成的边。这样以此类推。

# 算法核心 #

因此，可以对算法进行优化。设置一个队列，初始的时候将s放入队列中。  
【1】队列出队，出队元素为current，松弛current与其邻接点相连的边，将松弛成功的邻接点放入队列中，这些点中包含其最短路径的第二个点（第一个点为起点）  
【2】然后再次队列出队，出队元素为current，松弛current与其邻接点相连的边，但如果已在队列中就不要重复入队了  
【3】重复以上步骤  
其实这个步骤和[无权最短路径算法][Link 1]有点像。

# 代码实现 #

![这里写图片描述][2018070719040115]

from queue import Queue
    class Edge():
        def __init__(self,u,v,cost):
            self.u = u
            self.v = v
            self.cost = cost
    nodenum = 5
    
    edgeList = []
    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] = 0
        know[original] = True
        q.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.cost
                    if(temp < dis[edge.v]):#松弛操作
                        dis[edge.v] = temp
                        pre[edge.v] = current
                        if(not know[edge.v]):
                            q.put(edge.v)
                            know[edge.v] = True
            print('当前出队的元素为',current)
            print(dis)
            print(pre,'\n')
    
    SPFA(original)
    print('\n',dis)
    print(pre)

![这里写图片描述][70]  
从运行结果可以看出，程序的执行过程。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))

![2018070720090497][]  
如图所示，形成了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 = u
            self.v = v
            self.cost = cost
    nodenum = 5
    
    edgeList = []
    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] = 0
        know[original] = True
        q.put(original)
    
        while(not q.empty()):
            current = q.get()
            know[current] = False
            flag = False#负环判断标记
            #循环遍历current的邻接顶点
            for edge in edgeList:
                if(edge.u == current):#current点的邻接边
                    temp = dis[edge.u] + edge.cost
                    if(temp < dis[edge.v]):#松弛操作
                        dis[edge.v] = temp
                        pre[edge.v] = current
                        update[edge.v] += 1
                        for i in update:
                            if(i==nodenum):
                                flag =True
                                print('最后一次出队的是',current)
                                break
                        if(flag == True):
                            break
                        if(not know[edge.v]):
                            q.put(edge.v)
                            know[edge.v] = True
            if(flag == True):
                break
            print('当前出队的元素为',current)
            print(dis)
            print(pre,'\n')
    
    SPFA(original)
    print('dis',dis)
    print('pre',pre)
    print('update',update)

![这里写图片描述][70 1]  
运行结果并没有全部截图下来，因为中间执行了很多次不该有的出队入队操作（每次出队都输出东西），这里只截了最后结果。可以看到update数组中，有一个等于了5，所以程序就判断有了负权环。  
而且读者可以通过所有的输出结果，统计每个点出队次数，会发现，这些点里面出队次数最大也就为4（我用画正字来记的数==）。意思就是，如果程序通过出队次数来判断的话，那么程序还得多执行几次，不该有的出队入队操作。这也证实了，判断出队次数，是判断更新次数的上界。  
但通过所有输出结果，还是觉得程序判断出负权环判断得太迟了（中间执行了很多次不该有的出队入队操作），有没有一种更快的方法，可以及早判断出负权环呢。答案是有，如下。

## 根据最短路径上的死循环 ##

寻找最短路径的方法是通过pre数组：  
比如代码实现章节的程序运行后，pre数组为\[-1, 0, 1, 4, 1\]，要寻找从起点0到3的最短路径，步骤如下：  
【1】记录下3，路径为=>3  
【2】记录下pre\[3\]=4，路径为=>4=>3  
【3】记录下pre\[4\]=1，路径为=>1=>4=>3  
【4】记录下pre\[1\]=0，路径为=>0=>1=>4=>3  
【4】记录下pre\[0\]=-1，遇到-1，到达终点，返回路径=>0=>1=>4=>3  
从起点到某点的最短路径，路径上的点必定都是不重复的。但当有负权环时，这句话就不成立了。  
比如负权环章节的程序运行后，pre数组为\[-1, 3, 1, 2, 1\]，寻找从起点0到3的最短路径，会发现，上述步骤会一种进行下去，因为到达不了终点，死循环了（虽然这里程序是用的递归）。

#此程序用pre数组的死循环来判断是否有负环
    from queue import Queue
    class Edge():
        def __init__(self,u,v,cost):
            self.u = u
            self.v = v
            self.cost = cost
    nodenum = 5
    
    edgeList = []
    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 = 0
    
    
    def if_circle(pre):#判断是否有负权环，返回真假，如有负权环，并返回环
        prev = -1#设置环的起点
        circle = []#记录负权环
        def get(i):
            circle.append(i)
            if(i == -1):#到达了正常的终点，判断无负权环
                return False
            if(i == prev):#到达了不该达到的终点，判断有负权环
                return True
            return get(pre[i])
    
        for i in pre:
            if(i == -1):#超出索引限制了
                continue
            prev = i
            if(get(pre[i])):
                #传入参数直接是i的上一个顶点，直接传入i会出错
                return (True,circle)
            circle.clear()
    
        return (False,)
    
    
    def SPFA(original):
        q = Queue()
        dis[original] = 0
        know[original] = True
        q.put(original)
    
        while(not q.empty()):
            current = q.get()
            know[current] = False
            flag = False
            #循环遍历current的邻接顶点
            for edge in edgeList:
                if(edge.u == current):#current点的邻接边
                    temp = dis[edge.u] + edge.cost
                    if(temp < dis[edge.v]):#松弛操作
                        dis[edge.v] = temp
                        pre[edge.v] = current
                        if(if_circle(pre)[0]):
                            print('有负环为',if_circle(pre)[1])
                            print(dis)
                            print(pre)
                            flag = True
                            break
                        if(not know[edge.v]):
                            q.put(edge.v)
                            know[edge.v] = True
            if(flag == True):
                break
            print('当前出队的元素为',current)
            print(dis)
            print(pre,'\n')
    
    SPFA(original)
    print('\n',dis)
    print(pre)

![这里写图片描述][70 2]  
通过这种方式，程序可以很快地判断出来负权环（程序只出队了4次就判断出来了）。且得到了负权环的组成的点\[2, 1, 3\]。

[Bellman-Ford]: https://blog.csdn.net/anlian523/article/details/80953767
[Link 1]: https://blog.csdn.net/anlian523/article/details/80889649
[2018070719040115]: /images/20220521/1e50177ad761459abb79e5d401f9fc56.png
[70]: /images/20220521/74fb1ca209d24027bdbdfd569aa225ee.png
[2018070720090497]: /images/20220521/c84925e51f754cc4885b4f01c1d88171.png
[70 1]: /images/20220521/0daebfdf79f640f6aeeb349a12d3c631.png
[70 2]: /images/20220521/89e4d5a7a20246c5bf386b39fb9dbc6f.png