Python实现Dijkstra加权最短路径，节点3路径结果异常求助

问题背景 #

将PepCoding图基础模块中的「带权最短路径」问题从Java迁移到Python实现，需求是给定图和源顶点，输出源点到各顶点的最短路径及总距离。使用列表模拟优先队列，通过自定义Pair类的__lt__和__ge__方法实现排序，大部分结果正确，但源节点0到节点3的路径异常：

• 正确结果：3 via 012543 @ 30
• 当前输出：3 via 0123 @ 30

Java正确实现的Pair类compareTo方法 #

class Pair implements Comparable<Pair> {
    int distance;
    String path;
    int node;

    @Override
    public int compareTo(Pair o) {
        // 优先按距离升序排序
        if (this.distance != o.distance) {
            return Integer.compare(this.distance, o.distance);
        }
        // 距离相同时，按路径字符串字典序降序，确保目标路径优先被处理
        return o.path.compareTo(this.path);
    }
}

当前Python代码 #

class Pair:
    def __init__(self, node, distance, path):
        self.node = node
        self.distance = distance
        self.path = path

    # 仅按距离比较，未处理距离相等的情况
    def __lt__(self, other):
        return self.distance < other.distance

    def __ge__(self, other):
        return self.distance >= other.distance

def dijkstra(graph, source):
    import heapq
    n = len(graph)
    visited = [False] * n
    pq = []
    heapq.heappush(pq, Pair(source, 0, str(source)))

    while pq:
        current = heapq.heappop(pq)
        if visited[current.node]:
            continue
        visited[current.node] = True
        # 输出结果
        print(f"{current.node} via {current.path} @ {current.distance}")
        
        for neighbor, weight in graph[current.node]:
            if not visited[neighbor]:
                new_path = current.path + str(neighbor)
                new_dist = current.distance + weight
                heapq.heappush(pq, Pair(neighbor, new_dist, new_path))

# 示例图结构（匹配问题场景）
graph = [
    [(1, 10), (2, 1)],
    [(2, 2)],
    [(3, 20), (5, 3)],
    [],
    [(3, 1)],
    [(4, 2)]
]

dijkstra(graph, 0)

问题原因分析 #

1. 排序逻辑不一致：Java的compareTo方法在距离相等时，额外定义了路径的排序规则（按路径字典序降序），确保符合题目要求的路径优先从队列弹出并处理。
2. Python Pair类未处理距离相等场景：当前Python代码仅按距离升序排序，当两条路径到节点3的距离均为30时，队列会先弹出路径更短的0123，此时节点3被标记为已访问，后续符合要求的路径012543即使距离相同，也会因节点已被标记而被跳过，无法更新为最终结果。

修正方案 #

方案1：修正Pair类的排序逻辑 #

修改Pair类的比较方法，在距离相等时按题目要求的规则排序，确保正确路径优先被处理：

class Pair:
    def __init__(self, node, distance, path):
        self.node = node
        self.distance = distance
        self.path = path

    def __lt__(self, other):
        if self.distance != other.distance:
            return self.distance < other.distance
        # 距离相同时，按路径字典序降序，让符合要求的路径优先弹出
        return other.path < self.path

    def __ge__(self, other):
        if self.distance != other.distance:
            return self.distance >= other.distance
        return other.path >= self.path

方案2：优化Dijkstra逻辑（支持距离相同时更新路径） #

取消visited数组的直接判断，改为维护每个节点的最短距离和最优路径，遇到相同距离但更优的路径时强制更新：

def dijkstra(graph, source):
    import heapq
    n = len(graph)
    # 维护每个节点的最短距离和对应最优路径
    dist = [float('inf')] * n
    path = [""] * n
    dist[source] = 0
    path[source] = str(source)
    pq = []
    heapq.heappush(pq, Pair(source, 0, str(source)))

    while pq:
        current = heapq.heappop(pq)
        # 若当前路径距离大于已知最短距离，直接跳过
        if current.distance > dist[current.node]:
            continue
        # 若距离相等但路径更优，更新路径
        elif current.distance == dist[current.node] and current.path > path[current.node]:
            path[current.node] = current.path
        
        for neighbor, weight in graph[current.node]:
            new_dist = current.distance + weight
            new_path = current.path + str(neighbor)
            # 新距离更短，或距离相同但路径更优时，入堆更新
            if new_dist < dist[neighbor] or (new_dist == dist[neighbor] and new_path > path[neighbor]):
                dist[neighbor] = new_dist
                path[neighbor] = new_path
                heapq.heappush(pq, Pair(neighbor, new_dist, new_path))
    
    # 输出最终结果
    for i in range(n):
        print(f"{i} via {path[i]} @ {dist[i]}")

两种方案均可解决路径异常问题，方案2更灵活，适合需要在距离相同时选择特定路径的场景。

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