时间戳

首页 > 解决方案 > 为什么这个 Dijkstra 代码正确（节点处理）？

dijkstra - 为什么这个 Dijkstra 代码正确（节点处理）？

问题描述

https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/

我不太明白为什么这是真的。他们声称，通过检查current_distance > distances[current_vertex]，我们可以准确地处理每个节点一次。但是，这对我来说并不正确，因为 while 循环中的最后两行是

distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))

所以我认为每次一个节点被推到堆中时，如果它再次弹出并且我们观察到current_vertex, current_vertex（弹出的节点和权重），距离 [neighbor] 将等于 current_distance。因此，该节点将被重新处理，而不是像之前声称的那样被跳过。

import heapq


def calculate_distances(graph, starting_vertex):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[starting_vertex] = 0

    pq = [(0, starting_vertex)]
    while len(pq) > 0:
        current_distance, current_vertex = heapq.heappop(pq)

        # Nodes can get added to the priority queue multiple times. We only
        # process a vertex the first time we remove it from the priority queue.
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Only consider this new path if it's better than any path we've
            # already found.
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

有人可以告诉我我在这里缺少什么吗？我知道每个节点应该只处理一次，但我不明白为什么该代码会这样。而且我看不出我错在哪里。

标签： dijkstra

解决方案

顶点可以多次添加到堆中。每次它以不同的距离添加到堆中。现在，你终于处理它了。由于它是一个优先队列，因此您将处理(vertex, distance)距离最小的一对。

两个想法：

  1. 对于每个顶点，只有一个现有的（存在于堆中）对可以被处理。
  2. 处理完顶点后，不会添加此顶点的新对。

首先，到顶点的距离总是减小。这意味着对于给定的顶点，只有一个(vertex, distance)可以触发：即距离最小的那个（除非稍后到达更小距离的一对）。换句话说，当顶点被处理时，它在堆中的所有其他对都不会被处理。

顶点处理后，它的距离不能改变。原因是 Dijkstra 选择了距离最小的顶点；并且由于所有边权重都是正的，并且所有其他顶点的距离都更大，因此到已处理顶点的距离不会减小。因此，顶点的新对不能出现在堆中。

推荐阅读