基于DFS的有向图单源最短路径代码异常，请求排查

问题描述 #

用DFS实现的有向图单源最短路径函数，多数测试用例运行正常，但在特定用例中计算节点2的最短距离时出错：计算结果为123，正确值应为119。

原实现代码 #

def networkDelay(self,times,n,k):
    graph=collections.defaultdict(list)
    for u,v,w in times:
        graph[u].append((v,w))
    dist = [sys.maxsize] * (n + 1)
    dist[k] = 0
    visited=set()
    def dfs(graph,u,prev):
        visited.add((prev,u))
        for v,w in graph[u]:
            dist[v] = min(dist[v], dist[u] + w)
            if (u,v) not in visited:
                dfs(graph,v,u)
    dfs(graph,k,k)
    return dist[1:]

错误测试用例 #

输入：

times= [[2,7,63],[4,3,60],[1,3,53],[5,6,100],[1,4,40],[4,7,95],[4,6,97],[3,4,68],[1,7,75],[2,6,84],[1,6,27],[5,3,25],[6,2,2],[3,7,57],[5,4,2],[7,1,53],[5,7,35],[4,1,60],[5,2,95],[3,5,28],[6,1,61],[2,5,28]]
n=7,k=3

输出错误结果：dist[]=[90, 123, 0, 30, 28, 117, 57]

问题根源 #

1. 访问标记逻辑完全错误：代码中visited集合存储的是(prev, u)（进入节点u的边），但判断是否递归处理节点v的条件却是(u, v)是否在visited中，两者完全不匹配，导致本该处理的更新路径被错误阻断。
2. DFS本身不适合带权图最短路径：DFS是深度优先遍历，一旦沿着某条路径走到节点，就会优先探索该路径的后续节点，无法及时回溯处理后续出现的更短路径。即使标记逻辑正确，DFS也可能因无法重复更新节点距离，导致无法得到正确的最短路径。

在错误用例中，节点2的最短路径是3→5→4→1→6→2（总权重28+2+60+27+2=119），但原代码的标记逻辑导致当第一次通过其他路径到达节点6后，(u,6)被标记为已访问，后续通过更优路径到达6时，无法再处理6到2的边，最终节点2的距离未被更新为正确值。

修正方案 #

方案1：修正DFS逻辑（仅适合无环或特定场景） #

去掉错误的visited集合，改为只有当当前路径到节点u的距离比已记录的最短距离更小时，才递归更新邻接节点：

import collections
import sys

def networkDelay(self, times, n, k):
    graph = collections.defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = [sys.maxsize] * (n + 1)
    dist[k] = 0

    def dfs(u):
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                dfs(v)
    
    dfs(k)
    return dist[1:]

注意：该方案在存在环的图中可能出现无限递归，实际场景不推荐。

方案2：使用Dijkstra算法（推荐） #

对于带正权的有向图单源最短路径问题，Dijkstra算法是更高效且可靠的选择，实现如下：

import collections
import heapq
import sys

def networkDelay(self, times, n, k):
    graph = collections.defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = [sys.maxsize] * (n + 1)
    dist[k] = 0
    heap = []
    heapq.heappush(heap, (0, k))
    
    while heap:
        current_dist, u = heapq.heappop(heap)
        # 当前距离已大于记录的最短距离，无需处理
        if current_dist > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    # 若有节点无法到达，按题目要求返回-1（原代码返回dist[1:]可替换此行）
    max_dist = max(dist[1:])
    return max_dist if max_dist != sys.maxsize else -1

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