3
$\begingroup$

I was reading about Dijkstra algorithm and was referring two books 1) Introduction to Algorithms by Cormen Section 24.3 2) Algorithm design by Kleignberg Section 4.4

And found a subtle difference in their way of show Dijkstra algorithm

book 1:

Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while Q not equal to {}:
    u = Extract-Min(Q)
    S = S U {u}
    for each vertect v belonging to G.Adj[u] // all edges emanating from u
        Relax(u,v,w)

Note : the word in for each loop : G.Adj[u]

original snip from book

enter image description here

book 2:

Dijkstra(G, w, s)
Initialize(G,s) d(s) = 0 initialize others to inf
S = {}
Q = G.V
while S not equal to V:
    Select node v that is not yet added to S with at least one edge ***from S*** for which
         d'(v) = min of (d(u) + le)  // computed over all edges that 
                                     // emanate from all possible 
                                     // nodes in S
    Add v to S and make d(v) = d'(v)

Note : the word in for each loop : from S

original snip from book

enter image description here

Only I find one difference.

in book1 they are computing the neighbors of only the recently added node u. and in book2 they are computing neighbors of entire set S (see the highlighted portion "from S") (and that is not in S).

Yes, both works.

But why is there two implementations of Dijstra algorithm. Any reason why each book has adopted a different way ? Why should we do from entire S when we can easily do from last computed node as that is the one with the last node in the longest of the shortest path and that will decide everything ? Am I missing something ?

$\endgroup$
1
$\begingroup$

Usually algorithms are specified in a somewhat high level format. Later one might fine tune some of the implementation details to get the complexity right. Usually we call the various implementations all Dijkstra's algorithm. (And yes, I consider those implementation details, even though we are not coding in a specific language.)

  • How do we store the distances so that we easily find the one with shortest distance from the start node?

  • How do we store the graph: adjacency lists or adjacency matrix?

  • It might be a good idea to compute 'temporary' distances for nodes not yet completed, so that we do not have to look at all edges between nodes that are completed and those that are not yet completed.

In the special case of Dijkstra's algorithm the type of graphs we consider might influence the implementation details. We might choose a certain type of priority queue when the graphs are sparse or not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.