Dijkstra算法是做什么的
在一张图上,找单点到其他所有点的最小距离。
一找多
核心思路
每次循环都从所有没有确定最短距离的集合中,取已知最短距离最小的那个,并确定为已找到。并遍历他的邻居节点更新他们的距离。
为什么
我们反过来想,去一个点的最短路径应该是怎么样的,是不是应该是在这条路径上每个点的最短路径都是沿着这条路径的?
因为一旦有一个点的最短路径不沿着这条路径,那么后续所有的点都会有更短的路径可供更新。
我们截取一个快照。当一半的点已经被确定了,一半的点还未确定。那么我们就可以在未确定的点里面选已知最短路径最小的那个,把它放在确定集合里面,就行了。
假定这点叫做A.
首先,A的最短路径,肯定不会从那些同样没有确定最短路径的难兄难弟里面出现,因为去到它们那已经比到他那更远了,不要说接下来还有一段路走。
我们所有的路径长度都是正数
简单来说,就是一个大于x的数加一个正数,肯定只会大得更多。
那会不会有在已经确定的集合中出现推翻我们的结论的路径呢。这就是个坑了,因为我们已经把已经确定的集合遍历过了,有的话这条路径就已经更新在当前状态里面了,没有的话怎么推翻我们的结论呢?
那么在两边都考虑下,就能得到我们每次只需要把当前最小的拿出来做标记即可。
算法流程
一句话:每次从未确定(未做标记)的集合中取出当前最短距离最小的那个点,认为他可以加入到已确定的大家庭中。然后遍历他的所有邻居,对邻居进行更新即可。
对,就这么简单粗暴。后面可能看到复杂的代码实现和优化,但是核心还是这句话:
从未确定的集合中拿最小,遍历他做邻居的更新。
算法实现
首先我们需要一些数据结构来保存状态。从上文来看,我们需要一个集合V来保存已确定的节点,需要一个列表Dist来保存各个点当前的最小距离。一个MVP版本就是这样,足够了。
除此外,我们还有邻接表G和总节点集合S。
但是为了能明确路径是怎么走的,我们就像链表一样,给一个前驱节点保存的数据结构,可以写成一个结构体或类,当然也可以直接维护一个列表,我认为区别不大。
这个类的类元素可以是该节点的最短路径+前驱节点
然后我们便可以开始循环了。
首先从出发点开始,遍历他的邻接列表,然后如果能使得那些相邻点的距离变小,则更新那些点的最小距离和前驱节点。
在一开始,出发点就是这个距离最小的节点,手动确认或者循环确认都一样,因为他的距离就是0,自己到自己嘛。
然后把开始节点放入我们的V,这个循环就算是结束了。
下一个循环开始,我们又从S-V中找到一个已知距离最小的节点,遍历他的邻接列表,执行更新逻辑,然后把这个节点放进V中。
在一个循环体中,先放后放都没有影响,也可以在选中他后,就把他放进V中。
算法优化
如果要实现基于DIjkstra的最短路径算法,以上内容就足够了。但是如果真的动手写起代码来,就会发现一个问题:
找最小值。
我们每个循环都要找在S-V中的那些点里面,已知距离最小的那个。如果我们每次都是先在 Dist中按S-V去截取,这将产生巨大开销。
而我们知道,如果有频繁取最值的需求,堆是一个极其好用的数据结构。
我们就可以维护一个堆(Heap),把各个节点的最小距离丢进去,然后直接从这个最小堆里面去拿就行了。
懒更新
我们还能更进一步,放宽可能被确定的集合。
因为我们每次更新后,结果都有可能成为最小值。
首先最小值肯定产生于遍历和更新后的结果。因为从当前来看他就已经比之前的更小了,只不过我们不知道会不会有更小的。
既然如此,我就不去处理他,就丢进堆里面,然后加一个判断,如果他出堆的时候,这个点已经是被确定的,我们直接下一次循环就行了。
模板代码
下面我用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算法核心很简短,就是一句话:每次都从未确定的集合中拿最小,遍历他做邻居的更新。