python 中使用堆的 Dijkstra 算法的性能改进？

Question

下面是我使用堆（对于无向图）实现的 Dijkstra 算法。

这对于合理大小的图来说效果很好，但是我对重新计算连接到新探索节点的节点的贪婪标准的代码不满意。

这里我遍历了堆中的所有项目，这看起来不像是对数据结构的良好使用。有没有更好的方法来实现这一目标？

graph 是一个字典，其中包含每个节点（键）连接到它的节点列表和边的长度。 graph[v] returns [[w_1, l_1],...,[w_k, l_k]] 其中 v 和 w_i 之间有一条边，对于 1 和k.有点像邻接表。

shortestPath = {1: 0}  # Length of the shortest pass from s (labelled 1) to v (v's label = key)


def createHeap():
    # Heap contains the greedy criterion for an edge and the label of it's head vertex
    heap = []
    for k, v in graph.items():
        if k in shortestPath:
            continue  # Ignoring starting vertex
        bestScore = 1000000
        for (w, length) in v:
            if w in shortestPath:
                greedyScore = shortestPath[w] + length
                if greedyScore < bestScore:
                    bestScore = greedyScore
        hq.heappush(heap, (bestScore, k))  # bestScore used as heap key
    return heap


def dijkstra():
    heap = createHeap()
    for _ in range(n - 1):  # For every vertex in graph (other than starting vertex 1)
        greedyScore, w = hq.heappop(heap)  # Next vertex to be processed
        shortestPath[w] = greedyScore
        for [v, length] in graph[w]:  # Finds the new crossing edges and re-evaluates greedy criterion
            if v not in shortestPath:
                for item in heap:  # better implementation ?
                    if item[1] == v:
                        oldScore = item[0]
                        heap.remove(item)
                        hq.heapify(heap)
                        newScore = min(oldScore, greedyScore + length)
                        hq.heappush(heap, (newScore, v))

dijsktra()

Answer 1

有几种 Dijkstra 算法的替代实现，但其中 none 需要遍历堆，既不需要从堆中删除任意节点，也不需要重复 re-heapify。所有这些操作都会破坏堆旨在提供的性能优势。

我还建议避免使用全局变量。而是传递所需的参数作为参数，并让函数 dijkstra return 结果。

这是您可以用于 graph 数据结构的可能实现之一：

def dijkstra(graph, start):
    distances = {}
    heap = [(0, start)]

    while heap:
        dist, node = hq.heappop(heap)
        if node in distances:
            continue  # Already encountered before
        # We know that this is the first time we encounter node.
        #   As we pull nodes in order of increasing distance, this 
        #   must be the node's shortest distance from the start node.
        distances[node] = dist
        for neighbor, weight in graph[node]:
            if neighbor not in distances:
                hq.heappush(heap, (dist + weight, neighbor))

    return distances

调用示例：

graph = {
    "a": (("b", 8), ("c", 3), ("d", 6)),
    "b": (("a", 8), ("e", 5)),
    "c": (("a", 3), ("d", 2), ),
    "d": (("a", 6), ("c", 2), ("e", 5), ("g", 3)),
    "e": (("b", 5), ("d", 5), ("f", 5)),
    "f": (("e", 5), ("g", 3), ("h", 6)),
    "g": (("d", 3), ("f", 3), ("h", 4)),
    "h": (("g", 4), ("f", 6))
}

distances = dijkstra(graph, "a")

print(distances)

输出：

{'a': 0, 'c': 3, 'd': 5, 'b': 8, 'g': 8, 'e': 10, 'f': 11, 'h': 12}

python 中使用堆的 Dijkstra 算法的性能改进？

Performance improvement for Dijkstra algorithm using heaps in python?

python

heap

dijkstra