优先队列，堆和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的地方插入itemchange(k, item)，将索引为k的元素修改为itemcontains(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]], []]