通用的深度优先搜索+图的应用2：最短路径
2020-06-28 本文已影响0人
腹黑君
问题介绍：
带权图上的最小权重问题，即从一个顶点到另一个顶点的最小权重问题
问题解决方法：
- BFS 广度优先搜索（如果没有权重，只计算边的数量，就退化为词梯问题）
- Dijkstra算法
算法介绍：
- 通过将所有图的顶点放入优先队列中，其中起始顶点设置距离为0，其他顶点设置距离为系统最大值
- 将距离最小的顶点出队，更新与出队顶点相连接的各个顶点的距离值（加上权重），更新堆并重排
- 重复2的操作，更新堆
-
完成所有顶点的出队，此时可输出所有顶点的权重值
image.png
算法代码如下：
from pythonds.garph import PriorityQueue, Graph, Vertex
def dijkstra(aGraph, start):
pq = PriorityQueue()
# 初始节点距离初始化为0
start.setDistance(0)
pq.buildHeap([(v.getDistance(), v) for v in aGraph])
while not pq.isEmpty():
# 将最小距离的顶点出队列
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)
时间复杂度分析：
image.png
