带通行费约束的最短路径代码与NetworkX结果不符，请求排查

你的自定义代码和NetworkX结果不一致，核心问题在于visited集合的使用逻辑错误，以及对多状态路径的处理缺失，具体分析如下：

错误原因 #

1. 过早标记节点为已访问，丢失有效路径 #

普通Dijkstra算法中，visited集合的作用是确保每个节点只处理一次——因为第一次弹出的路径就是该节点的最小权重路径。但在你的场景中，每个节点可能对应多条不同的路径：这些路径的总cost和总toll组合不同，即使某个节点被处理过（加入visited），后续可能存在一条到该节点的路径，cost稍高但toll更低，这条路径可能能延伸出满足toll ≤ max_toll约束的终点路径，甚至是cost更低的合法路径。

比如：

• 到节点A的路径1：cost=5，toll=10（超过max_toll=8）
• 到节点A的路径2：cost=6，toll=5（符合约束）

你的代码会先弹出路径1，将A加入visited；后续弹出路径2时，发现A已在visited中直接跳过，导致无法通过路径2继续探索到终点的合法路径。

2. 终点判断逻辑的潜在问题 #

当第一次弹出终点节点时，如果其总toll超过max_toll，你的代码会将终点加入visited，后续即使有符合约束的路径到达终点，也会因为visited的判断被跳过，最终返回inf，而NetworkX的无约束路径是存在的，这就导致结果不一致。

修正方案 #

替换visited集合，改用字典记录每个节点在不同总toll下的最小cost，确保只有更优的路径才会被处理：

import heapq
from collections import defaultdict

def dijkstra_with_toll_constraint(G, start, end, max_toll):
    pq = [(0, start, 0, [start])]  # (总cost, 当前节点, 总toll, 路径)
    # 记录(node, toll)对应的最小cost，避免重复处理低效路径
    best = defaultdict(lambda: float('inf'))
    best[(start, 0)] = 0

    while pq:
        cost, node, toll, path = heapq.heappop(pq)
        
        # 优先队列按cost排序，第一个到达终点且符合约束的就是最小cost路径
        if node == end and toll <= max_toll:
            return cost, toll, path
        
        # 如果当前路径不是该节点该toll下的最优解，直接跳过
        if cost > best[(node, toll)]:
            continue
        
        for neighbor in G.neighbors(node):
            edge_cost = G[node][neighbor]["cost"]
            edge_toll = G[node][neighbor]["toll"]
            next_cost = cost + edge_cost
            next_toll = toll + edge_toll
            
            # 检查toll约束，且该路径比已记录的同状态路径更优
            if next_toll <= max_toll and next_cost < best[(neighbor, next_toll)]:
                best[(neighbor, next_toll)] = next_cost
                heapq.heappush(pq, (next_cost, neighbor, next_toll, path + [neighbor]))

    return float("inf"), float("inf"), None

修正说明 #

• 用best字典替代visited，允许同一节点存在多条不同toll的路径，只保留同状态下的最小cost路径，避免丢失有效探索分支。
• 弹出队列元素时先校验是否为当前状态的最优路径，避免无效计算。
• 当max_toll足够大（大于等于无约束路径的总toll），修正后的代码会和NetworkX的nx.dijkstra_path(G, 0, 49, weight="cost")结果一致。

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