Python实现Dijkstra算法的冗余检查问题及最优实现咨询

关于你提到的实现版本的疑问解答 #

你对Dijkstra算法核心逻辑的理解是正确的：节点一旦确定了最短路径，确实不需要再重复处理。但你提供的这个实现本身没有错误，这是工业界非常常见的一种简化实现思路，和教科书里带visited集合的版本只是取舍不同，不能直接判定为质量差：

• 你看到的"重复计算邻居距离"的开销非常小，只是O(1)的算术运算和判断，在判断distance < distances[neighbor]的时候就会直接丢弃无效值，不会进入优先队列产生更高开销。
• 这个实现不维护visited集合的写法更简洁，减少了额外集合维护的代码，降低了写错的概率，在稀疏图场景下性能损失几乎可以忽略。

适配相同图结构的最佳实践版本 #

我们可以把两种思路的优势结合，既加visited集合减少不必要的邻居遍历，又保留原有的距离判断做兜底，兼顾性能和鲁棒性，代码如下：

import heapq

def calculate_distances(graph, starting_vertex):
    # 初始化所有节点距离为无穷大
    distances = {vertex: float('inf') for vertex in graph}
    distances[starting_vertex] = 0
    # 已访问集合：标记已经确定最短路径的节点
    visited = set()
    # 优先队列：存储(当前距离, 节点)
    pq = [(0, starting_vertex)]
    
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        # 已经处理过的节点直接跳过
        if current_vertex in visited:
            continue
        # 距离大于已记录的最短距离，直接跳过（兜底逻辑）
        if current_distance > distances[current_vertex]:
            continue
        # 标记为已处理
        visited.add(current_vertex)
        
        for neighbor, weight in graph[current_vertex].items():
            # 已经处理过的邻居不需要再计算
            if neighbor in visited:
                continue
            new_distance = current_distance + weight
            # 只有新路径更短的时候才更新
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heapq.heappush(pq, (new_distance, neighbor))
    
    return distances

# 测试用例和你提供的完全一致
example_graph = {
    'U': {'V': 6, 'W': 7},
    'V': {'U': 6, 'X': 10},
    'W': {'U': 7, 'X': 1},
    'X': {'W': 1, 'V': 10}
}
print(calculate_distances(example_graph, 'U'))

这个版本和你提供的原版本输出完全一致，但是会减少很多不必要的邻居遍历，在稠密图场景下性能提升明显，同时代码逻辑清晰，适合学习和生产环境使用。

内容的提问来源于stack exchange，提问作者Robin Andrews