反向Dijkstra算法

Question

我已经开始在python中向后实现Dijkstra的算法：

def backwardsDijkstra(g: DoubleDictGraph, s, t):
    q = PriorityQueue()
    dist = {}
    next = {}
    q.add(t, 0)
    dist[t] = 0
    found = False
    while not q.isEmpty() and not found:
        x = q.pop()
        for y in g.parseNin(x):
            if y not in dist.keys() or dist[x] + g.Cost(x, y) < dist[y]:
                dist[y] = dist[x] + g.Cost(x, y)
                q.add(y, dist[y])
                next[y] = x
        if x == t:
            found = True
    return dist[s], next

我不明白为什么它会在下一张图的第二次迭代中停止，例如：

5 7
0 1 5
0 2 20
1 2 10
1 3 30
2 3 5
2 4 20
3 4 10
(number of vertices, number of edges, (start,end,cost)

Answer 1

代码中的bug在下面这一行：

        if x == t:
            found = True

因为您是从t (目标)开始的，所以您应该查找s (源)。目前，您正在跳出第一个候选者(即t)的循环。