7.8图的应用：最短路径问题

最短路径问题：Dijkstra算法

❖解决带权最短路径问题的经典算法是以发明者命名的“Dijkstra算法”
❖这是一个迭代算法，得出从一个顶点到其余所有顶点的最短路径，很接近于广度优先搜索算法BFS的结果
❖具体实现上，在顶点Vertex类中的成员dist用于记录从开始顶点到本顶点的最短带权路径长度（权重之和），算法对图中的每个顶点迭代一次
❖顶点的访问次序由一个优先队列来控制，队列中作为优先级的是顶点的dist属性。
❖最初，只有开始顶点dist设为0，而其他所有顶点dist设为sys.maxsize（最大整数），全部加入优先队列。
❖随着队列中每个最低dist顶点率先出队
❖并计算它与邻接顶点的权重，会引起其它顶点dist的减小和修改，引起堆重排
❖并据更新后的dist优先级再依次出队

# 最短路径
# 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)