Dijkstra算法

26 年 7 月 16 日 星期四
1455 字
8 分钟

Dijkstra算法是做什么的

在一张图上,找单点到其他所有点的最小距离。

一找多

核心思路

每次循环都从所有没有确定最短距离的集合中,取已知最短距离最小的那个,并确定为已找到。并遍历他的邻居节点更新他们的距离。

为什么

我们反过来想,去一个点的最短路径应该是怎么样的,是不是应该是在这条路径上每个点的最短路径都是沿着这条路径的?

因为一旦有一个点的最短路径不沿着这条路径,那么后续所有的点都会有更短的路径可供更新。

我们截取一个快照。当一半的点已经被确定了,一半的点还未确定。那么我们就可以在未确定的点里面选已知最短路径最小的那个,把它放在确定集合里面,就行了。

假定这点叫做A.

首先,A的最短路径,肯定不会从那些同样没有确定最短路径的难兄难弟里面出现,因为去到它们那已经比到他那更远了,不要说接下来还有一段路走。

我们所有的路径长度都是正数

简单来说,就是一个大于x的数加一个正数,肯定只会大得更多。

那会不会有在已经确定的集合中出现推翻我们的结论的路径呢。这就是个坑了,因为我们已经把已经确定的集合遍历过了,有的话这条路径就已经更新在当前状态里面了,没有的话怎么推翻我们的结论呢?

那么在两边都考虑下,就能得到我们每次只需要把当前最小的拿出来做标记即可。

算法流程

一句话:每次从未确定(未做标记)的集合中取出当前最短距离最小的那个点,认为他可以加入到已确定的大家庭中。然后遍历他的所有邻居,对邻居进行更新即可。

对,就这么简单粗暴。后面可能看到复杂的代码实现和优化,但是核心还是这句话:

从未确定的集合中拿最小,遍历他做邻居的更新。

算法实现

首先我们需要一些数据结构来保存状态。从上文来看,我们需要一个集合V来保存已确定的节点,需要一个列表Dist来保存各个点当前的最小距离。一个MVP版本就是这样,足够了。

除此外,我们还有邻接表G和总节点集合S。

但是为了能明确路径是怎么走的,我们就像链表一样,给一个前驱节点保存的数据结构,可以写成一个结构体或类,当然也可以直接维护一个列表,我认为区别不大。

这个类的类元素可以是该节点的最短路径+前驱节点

然后我们便可以开始循环了。

首先从出发点开始,遍历他的邻接列表,然后如果能使得那些相邻点的距离变小,则更新那些点的最小距离和前驱节点。

在一开始,出发点就是这个距离最小的节点,手动确认或者循环确认都一样,因为他的距离就是0,自己到自己嘛。

然后把开始节点放入我们的V,这个循环就算是结束了。

下一个循环开始,我们又从S-V中找到一个已知距离最小的节点,遍历他的邻接列表,执行更新逻辑,然后把这个节点放进V中。

在一个循环体中,先放后放都没有影响,也可以在选中他后,就把他放进V中。

算法优化

如果要实现基于DIjkstra的最短路径算法,以上内容就足够了。但是如果真的动手写起代码来,就会发现一个问题:

找最小值。

我们每个循环都要找在S-V中的那些点里面,已知距离最小的那个。如果我们每次都是先在 Dist中按S-V去截取,这将产生巨大开销。

而我们知道,如果有频繁取最值的需求,堆是一个极其好用的数据结构。

我们就可以维护一个堆(Heap),把各个节点的最小距离丢进去,然后直接从这个最小堆里面去拿就行了。

懒更新

我们还能更进一步,放宽可能被确定的集合。

因为我们每次更新后,结果都有可能成为最小值。

首先最小值肯定产生于遍历和更新后的结果。因为从当前来看他就已经比之前的更小了,只不过我们不知道会不会有更小的。

既然如此,我就不去处理他,就丢进堆里面,然后加一个判断,如果他出堆的时候,这个点已经是被确定的,我们直接下一次循环就行了。

模板代码

下面我用python实现这个算法:

Python
def dijkstra_solve(node):    
    pq=[]
    dist[node]=0
    visited[node]=True
    if node not in G:
        return
    for v,w in G[node]:
        if w<dist[v]:
            dist[v]=w
            heapq.heappush((w,v))
    while pq:
        mw,mv=heapq.pop(pq)
        ## 懒更新
        if visited[mv]:
            continue    
        visited[mv]=True
        if mv not in G:
            continue
        for v,w in G[mv]:
            if w+dist[mv]<dist[v]:
                dist[v]=w+dist[mv]
                head[mv]=mv
                heapq.heappush((dist[v],v))

没有具体的场景,数据输入输出就不写了。和上面命名一致,前驱节点采用的是维护一个列表实现的。

总结

dijkstra算法核心很简短,就是一句话:每次都从未确定的集合中拿最小,遍历他做邻居的更新。