SPFA

一种基于松弛的最短路算法 (支持负权!! 可算闭环!!)

算法思路:

OVO 小洪觉得遍历方法有点像广搜!
先遍历一个点的相邻区域,然后通过松弛方法判断是否更新起点到该点的最短路值(不要着急,松弛方法我们后面讲!)
更新了我们还要判断该点是否在队列里,若不在,才将该点加入队列。当队列为空时,即没有可松弛的点,我们结束遍历。

算法小步骤

首先我们要用到队列

from queue import Queue

然后开一个列表relax[ ],列表存储信息为起点到该点的最短路径值,创建时默认数值无穷大。

relax = [maxx for i in range(n+1)]
relax[s] = 0  #起点本身数值为0

写入数据,一般输入格式都是两个点和两点间的权值,为了方便后面遍历,我们可以采用链式前向星方法存储数据。

inf = [[] for i in range(n+1)]  #创建一个长度为n的空数组 n为地点数目
for i in range(r):
    a, b, c = map(int,input().split())
    inf[a].append([b,c])
    inf[b].append([a,c])        #若是单向路径,则不写此行

创建一个空队列,将起点s放进去

q = Queue()
q.put(s) 

这里我们讲一讲松弛方法,因为relax[ ]列表存储的是起到到该点的最小值。若len(A,B)表示点A到点B的权,我们只需要判断relax[A] + len(A,B) < relax[B],若成立,说明起点到点B的最短路是经过点A的这条,我们就需要更新relax[B]
QAQ应该说的很简单明了!
开始遍历!

while not q.empty():
    u = q.get()
    for i in range(len(inf[u])):
        if relax[inf[u][i][0]] > inf[u][i][1] + relax[u]:
            relax[inf[u][i][0]] = inf[u][i][1] + relax[u]
            if inf[u][i][0] not in q.queue:
                q.put(inf[u][i][0])

最后,relax[ ]存储的就是从起点到该点的最小值!!



dijistra算法

只要是在非负权图上找最短路,优先使用! 速度超级超级快!!
刚学快被这个搞哭了QAQ

算法思路

简单来说,我们有两个集合A和B,A集合里面存放已经确定好最短路的点和从起点到该点的最短路值,B集合存放未确定最短路的点和从起点到该点的路线值。每一次遍历,我们从B集合中找出路线值最短的点放入A集合,然后松弛B集合中各点的路线值。直到B集合中没有元素,结束遍历。

(思路看不懂就算了,我们跟着小步骤走~)

算法小步骤

首先,因为每次遍历我们都是从B集合中选择路线最短的点,我们使用优先队列(PriorityQueue)进行优化。
注:在使用优先队列时,我们无法删除队列里的旧节点,只能插入权值更小编号相同的点,所以优先队列会出现冗余。

from queue import PriorityQueue

我们使用relax[ ]记录起点到该点的路线值,初始默认为无穷大,起点到本身的路线值为0。

relax = [maxx for i in range(n+1)]
relax[s] = 0

同样,在存储数据时,我们还是使用链式前向星方法,方便遍历。

inf = [[] for i in range(n+1)]
for i in range(m):
    u,v,w = map(int,input().split())
    inf[u].append([v,w])
    inf[v].append([u,w])  # 单向路线不用写此行

在代码中,我们不需要按照思路创建两个集合存放各点,可以使用一个列表mark[ ]表示该点是否已经确定了最短路线值。
初始时,我们规定各点都还未确定最短路线。

mark = [False for i in range(n+1)]

创建一个空的优先队列,将起点放入队列中。存储时,我们可以以元组的形式存储,优先队列默认优先级是从小到大输出
小技巧:元组存储的格式为(距离,点)相同点时会优先输出距离最短的组合!

pq = PriorityQueue()
pq.put((relax[s],s))

开始遍历,当优先队列为空时,即B集合中没有元素,遍历停止。

while not pq.empty():
    k,point = pq.get()                    # k是从起点到point的最短距离
    if not mark[point]:                   # 相同序号的点可能被松弛多次(这就是优先队列的冗余情况)
        mark[point] = True                
        for i in range(len(inf[point])):       
            if k + inf[point][i][1] < relax[inf[point][i][0]]:
                relax[inf[point][i][0]] = k + inf[point][i][1]
                pq.put((relax[inf[point][i][0]],inf[point][i][0]))

最后,relax[ ]存储的就是从起点到该点的最小距离。

浅谈算法

大家看完算法,应该会惊讶这两个算法的板子特别像!
SPFA使用的是队列,遍历的本质其实是广搜,优先判断所有相邻点,然后进行松弛操作,每松弛一次,最短边数至少加一。
Dijistra使用的是优先队列(堆),遍历优先找最短边(本质是一个相邻点),然后进行松弛操作,同样,每松弛一次,最短边数至少加一。
大家都知道,在一个图中,最短边数最多是n-1条,当SPFA算法松弛超过了n-1次,说明图中存在负环,而Dijistra算法最多松弛n-1次。
最后,Dijistra算法其实可以看作特殊的SPFA,因为Dijistra算法中有一个mark[]判断该点是否记录过,所有它最多松弛n-1次,当我们把这个记录去掉,Dijistra的性能就和SPFA差不了。

Last modification:April 22nd, 2020 at 10:07 pm
如果觉得我的文章对你有用,请随意赞赏