优先队列,堆和Dijkstra算法
Opened this issue · 4 comments
优先队列
优先队列是一种 ADT,队列满足 FIFO,优先队列满足最大/最小元素先出。
堆
二叉堆
假设一棵二叉树,满足每个结点都大于等于/小于等于两个子结点,那这个二叉树就是堆有序的(heapified)。这样的二叉树可以按层级保存成一个数组。
上浮和下潜
我们考虑一个最大二叉堆 mh
,即根结点是最大的结点。方法 less(i,j)
给出第 i
个元素是否小于第 j
个元素。
当我们在 k
位置插入了一个较大的新元素的时候,我们想让这个堆重新有序,就需要把这个新元素和前面的元素交换。这个过程叫做 swim
。因为 k
位置的父结点就是 k/2
结点,所以
def swim(self, k):
while (k > 1 && less(k/2, k)):
exch(k/2, k)
k = k/2
相反的情形是,插入了一个较小的元素,这时就需要和后面的元素交换,这个过程叫做 sink
。在两个子结点中,我更希望和较大的那个交换,所以
def sink(self, k):
while (k*2 <= N):
j = k*2
if (j < N && less(j, j+1)):
j = j+1
if less(k,j):
exch(k, j)
k = j
else:
break
基于堆的优先队列
优先队列的插入,就是在数组的末尾插入一个元素,并从这个位置开始上浮。
优先队列的删除,就是把位置为 1 的元素和最后一个元素交换,最后一个元素出列,然后从 1 开始下潜。
索引最小优先队列
索引最大/最小优先队列是一种更特殊的优先队列,例如索引最小优先队列可能支持
insert(k, item)
,在索引为k
的地方插入item
change(k, item)
,将索引为k
的元素修改为item
contains(k)
,是否存在索引为k
的元素delete(k)
,删除索引为k
的元素min()
,返回最小的元素minIndex()
,返回最小的元素的索引delMin()
,删除最小的元素,并返回这个元素的索引isEmpty()
,队列是否为空size()
,队列的规模为多少
下面我们考虑用堆构造一个索引最小优先队列(下面简称 IndexMinPQ,或者 PQ)。
我们用 n
表示一个 PQ 的已经存入的元素,因为现在的 ADT 多了索引结构,所以我们用 keys
保存元素的值,用 pq
表示一个最小二叉堆。
例如执行 insert(2, 'shanghai')
,我们会让 keys[2] = 'shanghai'
并且 pq[n] = 2
,然后 swim(n)
会修改 pq
,不会修改 keys
。
如果要 change(3, 'beijing')
,我们就让 keys[3]='beijing'
,然后找到 pq[x] = 3
,执行 swim(x)
和 sink(x)
。
为了方便我们再引入一个变量 qp
满足
pq[qp[i]] = qp[pq[i]] = i
实现
class IndexMinPQ(object):
'''
'''
def __init__(self,maxN):
self.n = 0
self.keys = [None for i in range(maxN + 1)]
self.pq = [None for i in range(maxN + 1)]
self.qp = [-1 for i in range(maxN + 1)]
# 不涉及修改的方法
def isEmpty(self):
return self.n == 0
def contains(self, k):
return self.qp[k] != -1
def size(self):
return self.n
# 堆的方法
def greater(self, i, j):
return self.keys[self.pq[i]] > self.keys[self.pq[j]]
def exch(self, i, j):
swap = self.pq[i]
self.pq[i] = self.pq[j]
self.pq[j] = swap
self.qp[self.pq[i]] = i
self.qp[self.pq[j]] = j
def swim(self, k):
while (k > 1 and self.greater(k//2, k)):
self.exch(k, k//2)
k = k//2
def sink(self, k):
while (2*k <= self.n):
j = 2*k
if (j < self.n and self.greater(j, j+1)):
j = j+1
if self.greater(k, j):
self.exch(k, j)
k = j
else:
break
# 涉及修改的方法
def insert(self, i, key):
if not self.contains(i):
self.n += 1
self.qp[i] = self.n
self.pq[self.n] = i
self.keys[i] = key
self.swim(self.n)
else:
self.change(i, key)
def change(self, i, key):
self.keys[i] = key
self.swim(self.qp[i])
self.sink(self.qp[i])
def delete(self, i):
index = self.qp[i]
self.exch(index, self.n)
self.n -= 1
self.swim(index)
self.sink(index)
self.keys[i] = None
self.qp[i] = -1
# 涉及最小元素的方法
def min(self):
return self.keys[self.pq[1]]
def minIndex(self):
return self.pq[1]
def delMin(self):
min = self.pq[1]
self.exch(1, self.n)
self.n -= 1
self.sink(1)
self.qp[min] = -1
self.keys[min] = None
return min
最短路径问题
我们先给出一个加权有向图的数据结构
class EdgeWeightedDigraph(object):
def __init__(self, n):
self.v = n
self.e = 0
self.adj = [[] for i in range(n)]
def addEdge(self, edge):
# edge 是如同 [1,2,3] 的列表, 表示从 1 到 2, 权重为 3
self.e += 1
self.adj[edge[0]].append(edge)
下面给出一个定理:令 G 是一幅加权有向图,s 是 G 中的起点,distTo 是一个由顶点索引的数组,保存 G 中路径的长度,即 distTo[w]
- 当 w = s 时,等于 0
- 当 s 可以到达 w 时,等于某条路径的长度
- 当 s 不可以到达 w 时,等于 INF
当且仅当对于所有的边 e,其从 v 指向 w,满足 distTo[w] <= distTo[v] + e.weight 时,distTo 保存的是最短边的长度。
必要性是显然的。要证明其充分性的话,考虑一条最短路径 s=v0 -> v1 -> ... -> vk=w,令 ei 表示 vi-1 指向 vi 的边,我们有
distTo[w]
= distTo[vk]
<= distTo[vk-1] + ek.weight
<= distTo[vk-2] + ek-1.weight + ek.weight
<= ...
<= distTo[v0] + e1.weight + ... + ek.weight
= distTo[s] + e1.weight + ... + ek.weight
= 0 + e1.weight + ... + ek.weight
= e1.weight + ... + ek.weight
因为 e1 -> ... -> ek 已经是最短路径了,所以整个不等式不可能取小于号,两侧必然相等。所以distTo 保存的是最短边的长度。
由于这个定理的存在,我们要找一个图上的一棵起点为 s 的最短路径树,只要把 distTo 初始化为 distTo[s]=0,其他元素均为 INF,然后执行边的松弛,直到无法继续松弛为止就可以了。
下面给出一个例子
class EdgeWeightedDigraph(object):
def __init__(self, n):
self.v = n
self.e = 0
self.adj = [[] for i in range(n)]
def addEdge(self, edge):
# edge 是如同 [1,2,3] 的列表, 表示从 1 到 2, 权重为 3
self.e += 1
self.adj[edge[0]].append(edge)
def addEdges(self, edges):
for edge in edges:
self.addEdge(edge)
INF = float('inf')
class SP(object):
def __init__(self, ewdg, s):
self.ewdg = ewdg
self.s = s
self.distTo = [INF for i in range(ewdg.v)]
self.edgeTo = [[] for i in range(ewdg.v)]
self.distTo[s] = 0
def relax(self, edge):
v = edge[0]
w = edge[1]
if (self.distTo[w] > self.distTo[v] + edge[2]):
self.distTo[w] = self.distTo[v] + edge[2]
self.edgeTo[w] = self.edgeTo[v] + [edge]
def relax_loop(self):
for i in range(self.ewdg.v):
for edge in self.ewdg.adj[i]:
self.relax(edge)
if __name__ == "__main__":
g = EdgeWeightedDigraph(5)
edges = [[0,1,1], [0,2,1], [1,3,2], [2,3,0.5], [0,3,2]]
g.addEdges(edges)
sp = SP(g, 0)
sp.relax_loop()
print(sp.distTo)
print(sp.edgeTo)
输出是
[0, 1, 1, 1.5, inf]
[[], [[0, 1, 1]], [[0, 2, 1]], [[0, 2, 1], [2, 3, 0.5]], []]
有时候一遍 relax_loop 还没有满足最优性条件,那我们就再执行一遍,直到执行 relax_loop 不改变 distTo 的值为止。
Dijkstra 算法
下面考虑一个所有边的权都非负的加权有向图。
Dijkstra 算法这样处理这幅图的单起点最短路问题:首先 distTo 全部初始化为 inf,distTo[s]=0,然后放松 distTo 中最小的顶点。
下面给出证明:考虑两个相邻的顶点 v 和 w,假设 v 是 s 可到达的,因为所有边的权都非负,那么当每一条 v 指向 w 的边被放松时,distTo[w] 只会减小,而 distTo[v] 不会改变。
实现
INF = float('inf')
class SP(object):
def __init__(self, ewdg, s):
self.ewdg = ewdg
self.s = s
self.distTo = [INF for i in range(ewdg.v)]
self.edgeTo = [[] for i in range(ewdg.v)]
self.distTo[s] = 0
# Dijkstra
self.pq = IndexMinPQ(self.ewdg.v)
self.pq.insert(s,0.0)
while not self.pq.isEmpty():
v = self.pq.delMin()
self.relax_v(v)
def relax(self, edge):
v = edge[0]
w = edge[1]
if (self.distTo[w] > self.distTo[v] + edge[2]):
self.distTo[w] = self.distTo[v] + edge[2]
self.edgeTo[w] = self.edgeTo[v] + [edge]
self.pq.insert(w, self.distTo[w])
def relax_v(self, v):
for edge in self.ewdg.adj[v]:
self.relax(edge)
if __name__ == "__main__":
g = EdgeWeightedDigraph(5)
edges = [[0,1,1], [0,2,1], [1,3,2], [2,3,0.5], [0,3,2]]
g.addEdges(edges)
sp = SP(g, 0)
print(sp.distTo)
print(sp.edgeTo)
输出是
[0, 1, 1, 1.5, inf]
[[], [[0, 1, 1]], [[0, 2, 1]], [[0, 2, 1], [2, 3, 0.5]], []]