Dijkstra 算法伪代码 "U" 符号

Question

我目前正在尝试遵循 Dijkstra 算法的伪代码，但我很难理解其中一行的含义。

DijkstrasAlgorithm(G, w, s)
    InitalizeSingleSource(G, s)
    S = 0
    Q = G.V
    while Q != 0
        u = ExtractMin(Q)
        S = S∪{u}
        for each vertex v ∈ G.Adj[u]
            Relax(u, v, w)

这部分 "S = S∪{u}" 让我感到困惑。我不确定 S 应该等于什么。有人可以解释吗？谢谢！

Answer 1

那是 set union 运算符。这里的 S 是计算出最短路径的所有节点的集合，这一行的意思是“将节点 u 添加到该集合。”

从机制上讲，S ∪ {u} 是由 S 中已有的所有内容加上节点 u 组成的集合。所以S = S ∪ {u}的意思是把u加到S中。

（请注意，我认为伪代码在声明 S 的地方有错字。您可能打算将其初始化为空集 ∅ 而不是数字 0。）

Dijkstra 的算法是一种很难完全从伪代码中理解的算法。我建议查看某个地方的教程，以便您对正在发生的事情有一个高层次的直觉。通过将内容映射到您的概念理解，更容易理解此伪代码。