Dijkstra算法通过公开测试用例但隐藏用例失败，遗漏了哪些边界情况？

核心问题 #

你的实现不符合Dijkstra算法的标准逻辑，两个致命错误导致隐藏用例失败：

• 使用普通FIFO队列而非优先队列：你自行对当前节点的邻边排序的逻辑只能保证局部顺序，无法处理全局更短路径的更新场景。
• seen集合的标记逻辑错误：你在节点入队时就标记为已处理，后续如果出现到该节点的更短路径，也不会再处理该节点的邻边更新，直接丢失正确路径。
  你提供的公开测试用例刚好匹配你错误逻辑的遍历顺序，因此可以全部通过，但结构更复杂的隐藏用例就会触发错误。

修正方案 #

按照你贴出的成功用户的思路调整实现：使用PriorityQueue，每次入队插入(当前最短距离, 节点)的元组，允许同一个节点多次入队，弹出时如果发现当前元组的距离大于已记录的最短距离，直接跳过该条目即可，无需修改已入队的旧条目。

修正后完整代码 #

# Uses python3
import queue
import sys
from math import inf


def dijkstra(adj, cost, s, t):
    dist = [inf] * len(adj)
    dist[s] = 0
    # 优先队列存储（当前距离，节点编号）
    q = queue.PriorityQueue()
    q.put((0, s))

    while not q.empty():
        current_dist, n = q.get()
        # 弹出目标节点直接返回，已经是最短路径
        if n == t:
            return current_dist
        # 当前条目是旧的长路径，直接跳过
        if current_dist > dist[n]:
            continue
        # 遍历所有邻边
        for i, adjacent in enumerate(adj[n]):
            new_dist = current_dist + cost[n][i]
            if new_dist < dist[adjacent]:
                dist[adjacent] = new_dist
                q.put((new_dist, adjacent))

    return dist[t] if dist[t] is not inf else -1


def parse(input):
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(zip(data[0 : (3 * m) : 3], data[1 : (3 * m) : 3]), data[2 : (3 * m) : 3]))
    data = data[3 * m :]
    adj = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for ((a, b), w) in edges:
        adj[a - 1].append(b - 1)
        cost[a - 1].append(w)
    s, t = data[0] - 1, data[1] - 1
    return dijkstra(adj, cost, s, t)


if __name__ == "__main__":
    input = sys.stdin.read()
    print(parse(input))


def test_parse():
    assert 3 == parse(open("input.txt").read())
    assert 6 == parse(open("input.1.txt").read())
    assert -1 == parse(open("input.2.txt").read())
    assert 3 == parse(open("input.3.txt").read())
    assert 0 == parse(open("input.4.txt").read())
    assert 0 == parse(open("input.5.txt").read())

修正后的代码可以兼容你所有已有的测试用例，同时能正确处理所有隐藏场景，运行效率也符合要求。

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