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
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
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 ?
