Алгоритм Дейкстры, псевдокод, символ "U"

Question

В настоящее время я пытаюсь следовать псевдокоду для алгоритма Дейкстры, но мне трудно понять, что означает одна из строк.

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, плюс узел и.Вот почему S = S ∪ {u} означает добавление u к S.

(Как примечание, я думаю, что у псевдокода есть опечатка, в которой был объявлен S. Вы, вероятно, хотели инициализировать его пустым набором∅, а не число 0.)

Алгоритм Дейкстры довольно сложен для понимания исключительно из псевдокода.Я рекомендую проверить учебник где-нибудь, чтобы у вас была интуиция высокого уровня для того, что происходит.Намного легче понять этот псевдокод, отобразив содержимое на ваше концептуальное понимание.