最短路径问题：Dijkstra算法
❖解决带权最短路径问题的经典算法是以发明者命名的“Dijkstra算法”
❖这是一个迭代算法，得出从一个顶点到其余所有顶点的最短路径，很接近于广度优先搜索算法BFS的结果
❖具体实现上，在顶点Vertex类中的成员dist用于记录从开始顶点到本顶点的最短带权路径长度（权重之和），算法对图中的每个顶点迭代一次
❖顶点的访问次序由一个优先队列来控制，队列中作为优先级的是顶点的dist属性。
❖最初，只有开始顶点dist设为0，而其他所有顶点dist设为sys.maxsize（最大整数），全部加入优先队列。
❖随着队列中每个最低dist顶点率先出队
❖并计算它与邻接顶点的权重，会引起其它顶点dist的减小和修改，引起堆重排
❖并据更新后的dist优先级再依次出队
image.png
# 最短路径
# G - 无向赋权图
# start - 开始节点
# 返回从开始节点到其它所有节点的最短带权路径
from PriorityQueue import PriorityQueue
from Graph import Graph
def dijkstra(G, start):
pq = PriorityQueue() # 创建优先队列
start.setDistance(0) # 起点距离设置为0，其它节点距离默认maxsize
# 将节点排入优先队列，start在最前面
pq.buildHeap([(v.getDistance(), v) for v in G])
while not pq.isEmpty():
# 取从start开始距离最小的节点出队列，作为当前节点
# 当前节点已解出最短路径
currentVert = pq.delMin()
# 遍历节点的所有邻接节点
for nextVert in currentVert.getConnections():
# 从当前节点出发，逐个加上邻接节点的距离进行检验
newDist = currentVert.getDistance() + currentVert.getWeight(nextVert)
# 如果小于邻接节点原有距离，就更新邻接节点
if newDist < nextVert.getDistance():
# 更新距离值
nextVert.setDistance(newDist)
# 更新返回路径
nextVert.setPred(currentVert)
# 更新优先队列
pq.decreaseKey(nextVert, newDist)
需要注意的是，Dijkstra算法只能处理大于0的权重,如果图中出现负数权重，则算法会陷入无限循环
Dijkstra算法分析
❖首先，将所有顶点加入优先队列并建堆，时间复杂度为O(V)
❖其次，每个顶点仅出队1次，每次delMin花费O(logV)，一共就是O(VlogV)
❖另外，每个边关联到的顶点会做一次decreaseKey操作（O(logV))，一共O(ElogV)
❖上面三个加在一起 ， 数量级就是O((V+E)logV)
网友评论