在 python 中使用堆来提高 Dijkstra 算法的性能？

Question

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

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

在这里，我迭代了堆中的所有项目，这看起来并没有很好地利用数据结构。有没有更好的方法来实现这一目标？

图是一个字典，其中包含每个节点（键）与其连接的节点列表以及边的长度。 graph[v] 返回 [[w_1, l_1],...,[w_k, l_k]]，其中 v 之间有一条边对于 1 到 k 之间的所有 i，w_i 的长度为 l_i。有点像邻接表。

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的算法有几种替代实现，但是它们都不需要通过堆迭代，也不需要从中删除任意节点，也不需要重复重新使用它。所有这些动作都杀死了堆打算给予的绩效收益。

我还建议避免全球变量。而是将需要的内容作为参数传递，然后让函数dijkstra 返回结果结果。

这是您可以用于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}