Dijkstra 算法缺少什么边缘情况？

Question

这是我的 Dijkstra 实现。它通过了 pytest input.n.txt 文件中的所有案例，但是当我提交给评分软件（不提供测试或任何输出）时，我得到了无效结果。

这是我的解决方案（通过了所有提供的测试用例，但没有通过隐藏的测试用例）。

# Uses python3

import queue
import sys
from math import inf


def dijkstra(adj, cost, s, t):

    seen = set([s])

    dist = [inf] * len(adj)
    dist[s] = 0

    prev = [None] * len(adj)
    prev[s] = s

    q = queue.Queue()
    q.put(s)

    while not q.empty():

        n = q.get()
        # print(n)

        edges = []
        for i, adjacent in enumerate(adj[n]):
            edges.append([adjacent, cost[n][i]])

        for i, edge in enumerate(edges):
            d = dist[n] + edge[1]
            if d < dist[edge[0]]:
                dist[edge[0]] = d
                edge[1] = d
                prev[edge[0]] = n

        edges = sorted(edges, key=lambda x: x[1])
        for (e, w) in edges:
            if not e in seen:
                seen.add(e)
                q.put(e)

        # print(dist)

    # print(prev)

    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())

输入格式如下...

number_of_vertices number_of_edges
from to weight
from to weight
start end

input.txt

输入.1.txt

输入.2.txt

输入.3.txt

输入.4.txt

输入.5.txt

我的程序通过了所有这些。而且我已经尝试搞乱所有我能想到的测试边缘情况，但它仍然失败，并在测试软件中出现“错误答案”错误。

DID 解决者的帖子评论之一：

Wow! I really struggled to put this one together, not because I didn't understand the Dijkstra algorithm but because of the difficulty in adjusting the priority of an item already added to a Python PriorityQueue class (whose use was implied by importing queue in the start code) or by keeping track of its position in the priority queue, which made translating the algorithm, as presented in the lectures, verbatim difficult.

In case it is helpful to others, the way I got around this was to move from thinking in terms of inserting vertices to the priority queue to inserting references to the vertices, with most updated distance at the time of insertion as the priority, instead. That way we don't need to adjust the priority of an item already added to the queue at a later time.

We may end up inserting several references to the same vertex to the queue, but we will, of course, encounter the reference with the least distance first, and we can ignore any future references to the same vertex that we might encounter afterwards. Further, we can abort the algorithm as soon as we've popped a reference to the destination vertex.

This still runs pretty efficiently (for me, a maximum time of about a twentieth of that allowed), and is, in retrospect, a small adjustment in viewing the problem.

Answer 1

你的算法使用队列； Dijkstra 算法不使用队列。

在每次迭代中，您必须select具有最短路径距离的未确认顶点。这可以使用最小优先级队列来完成，其中路径距离是优先级，但还要注意，如果通过不同距离的不同路径发现每个顶点，则每个顶点可能必须多次添加到优先级队列中。（你的同学最初尝试以困难的方式做到这一点 - 通过更新优先级队列中已有顶点的优先级，而不是只允许每个顶点多次出现在优先级队列中。）

因此您的算法不是 Dijkstra 算法的正确实现，因为它按照发现顶点的顺序确认顶点，而不是按照距源顶点的路径距离的顺序。

Dijkstra 算法缺少什么边缘情况？

What edge case am I missing for Dijkstra's algorithm?

python

dijkstra