python 中的 Dijkstra 算法实现跟踪

Question

我正在尝试使用优先级队列追踪 Dijkstra 算法的 python 实现，但我无法理解，因为我是 python

的新手

这是实现

def dijkstra(edges, f, t):
    g = defaultdict(set)
    for l,r,c in edges:
        g[l].add((c,r))
        g[r].add((c, l))

    q, seen,  = [(0,f,())], set(),
    while q:
        (weight, v1, path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path += (v1,)
            if v1 == t:
                return weight, path
            for k, v2 in g.get(v1, ()):
                if v2 not in seen:
                    heappush(q, (weight+ k, v2, path))


    return float("inf")

首先为什么用g = defaultdict(set)而不是g = defaultdict(list) 并使用 .add() 而不是 .append()
我知道在 Dijkstra 算法的开头，您需要将所有节点的所有权重设置为无穷大，但我在这里没有看到。
同样，节点在哪条线上决定它要经过的路径，就像在哪条线上决定向左或向右走一样。简单来说，在代码中节点之间的加权线是在什么地方制作的。

解释代码每一行发生的事情的注释对我理解它非常有帮助。

Answer 1

关于您的问题：

first why did it use g = defaultdict(set) instead of g = defaultdict(list) and used .add() instead of .append()

它与 list 的效果一样好。当然，要使用的方法（add 或 append）来自这个选择。我能看到的唯一优点是使用 set 可以避免两次添加相同的边。通常，一个图在相同的两个顶点之间可以有多个边，它们甚至可以具有相同的权重：发生这种情况时，没有理由单独考虑这些重复边，set 将确保重复忽略边缘。

I understand that in the beginning of Dijkstra algorithm you need to to set all weights for all nodes to infinity but I don't see it here.

有多种方法可以实现该算法。实际上，您可以在一开始就将所有顶点添加到优先级队列中，其中除源顶点之外的所有顶点都以无穷大权重开始。但是从队列中排除那些“无穷大”的顶点会更有效一些：这样队列的大小会更小，并且添加到队列中的第一个顶点的添加速度会稍微快一些。所以任何不在队列中的顶点实际上是一个权重仍然为无穷大的顶点。

also in which lines the node decides the path it's going through like in what line the decision of going left or right is made . in simple word where in the code the weighted line between the nodes is made.

代码中没有可见的决定。在找到目标节点之前，所有路径都是潜在的赢家。在此之前，所有已构建的部分路径都在堆上，堆的特性决定了哪条路径将是下一条将扩展到相邻节点的路径。然后那些更长的路径（有更多的顶点）将再次被扔进堆中，堆的魔法将再次发挥作用。因此，如果您查找“决策”，则只会在堆内做出决策：它告诉我们堆中权重最小的路径是哪条。因此主循环可能在一条路径上工作一点（扩展它），但在下一次迭代中它可能在一条完全不同的路径上工作。如此继续下去，直到突然发现它已经到达了目标顶点。仅在那一刻，堆上仍然是候选者的所有其他路径都将被忽略。

如果您想更多地了解 heappop 和 heappush 的隐藏魔法，请阅读有关该主题的 Wikipedia article。

不是最优的

虽然算法是正确的，但它不是一个高效的实现。以下语句表示要复制的路径，并且该路径最多可能有 n 个元素，因此它的最坏情况时间复杂度为 O(n) 在一次执行中，算法的最坏情况时间复杂度为 O(n²logn):

path += (v1,)

为了避免这种情况，通常不跟踪整个路径，而是只存储对我们来自的前一个节点的反向引用。然后当我们到达目标节点的时候，我们可以沿着这些反向引用返回并只构建一次路径。由于存储反向引用需要常数时间，此改进将使算法的时间复杂度为 O(nlogn).

python 中的 Dijkstra 算法实现跟踪

Dijkstra's algorithm implementation tracing in python

python

algorithm

trace

dijkstra

不是最优的