Search code examples
pseudocodedijkstra

Dijkstra's Algorithm pseudocode "U" symbol

I'm currently trying to follow pseudocode for Dijkstra's Algorithm, but I'm having difficulty understand what one of the lines means.

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)

This part right here "S = S∪{u}" is what's confusing me. I'm not sure what S is supposed to be equal to. Could someone explain? Thanks!

Solution

  • That’s the set union operator. S here is the set of all nodes for which the shortest path has been computed, and this line means “add the node u to that set.”

    Mechanically, S ∪ {u} is the set consisting of everything already in S, plus the node u. That’s why S = S ∪ {u} means to add u to S.

    (As a note, I think the pseudocode has a typo in where S was declared. You probably meant to initialize it to the empty set ∅ rather than the number 0.)

    Dijkstra’s algorithm is a pretty tough one to understand purely from pseudocode. I recommend checking out a tutorial somewhere so that you have a high-level intuition for what’s going on. It’s much easier to understand this pseudocode by mapping the contents onto your conceptual understanding.