Dijkstra算法实现返回错误结果，请求排查问题（LeetCode场景）

我在做LeetCode上第一道Dijkstra算法题时遇到了问题，代码始终无法通过测试用例，不想参考别人的实现，希望自己找出问题。

测试用例：times=[[2,1,1], [2,3,1], [3,4,1]]，节点数n=4，源节点source=2，正确返回值应为2，但我的代码一直返回-1。我怀疑问题出在循环的条件判断里，自己梳理的邻接表如下：

{
    1: []
    2: [(1,1), (3,1)]
    3: [(4,1)]
    4: []
}

我的代码：

import heapq
from collections import defaultdict

def network_delay_time(times, n, source):
    """
    计算从源节点出发，网络中所有节点都收到信号的最小时间
    参数：
    times (List[List[int]]): 边列表，每个元素为(u, v, w)，表示u到v的耗时为w
    n (int): 网络中的节点总数
    source (int): 源节点
    返回：
    int: 所有节点收到信号的最小时间，若无法覆盖所有节点则返回-1
    """
    if not times:
        return None
    
    adj_dict = defaultdict(list)
    for start_node, target_node, edge_weight in times:
        adj_dict[start_node].append((target_node, edge_weight))

    visited = set()
    queue = [(source, 0)]
    distances_dict = {}

    for key in range(1,n+1):
        distances_dict[key] = float('inf')
    distances_dict[source] = 0

    while queue:
        current_node, edge_weight = heapq.heappop(queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor in adj_dict[current_node]:
            if neighbor[0] not in visited:
                distance = neighbor[1] + distances_dict[current_node]
                if distance < distances_dict[neighbor[1]]:
                    distances_dict[neighbor[1]] = distance
                    heapq.heappush(queue, (neighbor, distance))
                    print(visited)
            

    if len(visited) < n:
        print(visited)
        return -1
    else:   
        return max(distances_dict.values())

print(network_delay_time([[2,1,1], [2,3,1], [3,4,1]], 4, 2))

问题排查 #

你的代码存在三个关键错误，直接导致逻辑失效：

1. 堆元素格式错误
   初始化队列时用的是(source, 0)（节点+距离），但后续往堆里push的是(neighbor, distance)，而neighbor是(目标节点, 权重)的元组。这会导致弹出堆元素时，current_node变成了元组，无法正确匹配visited集合中的整数节点编号，最终很多节点无法被标记为已访问。

2. 距离字典索引错误
   更新距离时写的是distances_dict[neighbor[1]]，但neighbor[1]是边的权重，不是目标节点的编号！目标节点编号是neighbor[0]，这直接导致距离字典无法正确更新目标节点的最短路径值。

3. 不必要的邻接节点过滤
   你添加了if neighbor[0] not in visited:的判断，这违反了Dijkstra算法的逻辑——即使节点已被访问，堆中可能存在旧的、更长的路径条目，但算法会通过current_dist与已记录的最短距离对比来跳过，而不是提前过滤。这个限制会导致部分节点无法被加入堆中，比如测试用例里的节点4。

修正后的代码 #

import heapq
from collections import defaultdict

def network_delay_time(times, n, source):
    # 边界处理：无边且节点数大于1时，无法覆盖所有节点
    if not times and n > 1:
        return -1
    
    adj_dict = defaultdict(list)
    for start_node, target_node, edge_weight in times:
        adj_dict[start_node].append((target_node, edge_weight))

    visited = set()
    # 堆存储格式改为(累计距离, 节点)，让heapq按距离自动排序（更符合Dijkstra的常规实现）
    queue = [(0, source)]
    # 用字典推导式简化距离初始化
    distances_dict = {node: float('inf') for node in range(1, n+1)}
    distances_dict[source] = 0

    while queue:
        current_dist, current_node = heapq.heappop(queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        # 拆解邻接节点和权重，避免混淆
        for neighbor_node, edge_weight in adj_dict[current_node]:
            new_dist = current_dist + edge_weight
            if new_dist < distances_dict[neighbor_node]:
                distances_dict[neighbor_node] = new_dist
                heapq.heappush(queue, (new_dist, neighbor_node))

    max_time = max(distances_dict.values())
    # 若存在节点无法到达，max_time会是inf，返回-1
    return max_time if max_time != float('inf') else -1

print(network_delay_time([[2,1,1], [2,3,1], [3,4,1]], 4, 2))  # 输出2

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