Dijkstra's algorithm in CLRS, p.595 has the following code in line 7:
for each vertex v \in Adj[u]
This line picks to iterate on all neighbors of node v. Node v here is the one the algorithm is currently processing and adding to the shortest path tree. However, among those neighbors of v, those already in set S are processed on & done with, and those nodes in S are forming a shortest path tree T. None of the nodes in set S can have a path-thru-v that is shorter than a path already in T. Otherwise, that path would have been traversed till then.
So, shouldn't this line 7 be better as
for each vertex v \in Adj[u] \intersect Q // Q = V \ S
or, equally,
for each vertex v \in Adj[u]\S
?
//===========================
ADDING explanations:
once you processed (processed=set the distance and parent vector entries of all its immediate neighbors) a node u and added it to the tree, that node u is at shortest distance from the source. if there were an off-tree node z so that a shorter path to u would exist thru it between the source & u, that node z would be processed before u.
//======================
ADDITION 2: lengthy comment to Javier's useful answer below:
Put all edges in the graph in an array say "EDGES"-- one edge, one array entry. each array entry holds the edge (u,v), the edge-weight, and 2 pointers-- one to node u and one to node v.
the graph is represented still as an adjacency list.
Adj[u] is still a linked list-- however, this linked list is on an array structure. The node values in this list, this time, is the index of EDGES corresponding to that edge.
So, for instance, Node u has 2 links incident to it: (u,x) & (u,y). Edge (u,x) is sitting at the 23rd cell of EDGES and (u,y) at 5th. Then, Adj[u] is a linked list of length 2, the nodes in this list are 23 and 5. Say, Adj[u][0].edgesIndex=23 and Adj[u][1].edgesIndex=5. Here, Adj[x][i].edgesIndex=23 for some i in the linked list at Adj[x] as well. (Adj[j][i], being a node in a linked list, further hast the "next" and "prev" fields on it.)
And, EDGES[23] has one reference to the corresponding entry of (u,x) on Adj[u], and another to that of Adj[x]. I leave line 7 as is, but this time, after i process an edge (u,v) in that loop, (i've found out about this edge from Adj[u]), i remove that edge from the linked list of Adj[u], from there i go to the corresponding EDGES entry, which has the reference to the corresponding Adj[x][i] entry. i remove them all-- EDGES[23], Adj[u][0] and Adj[x][i] (whatever i is there.) With all arrays-structures, i can process all these in constant time for each edge.
Still the adjacency list representation, can trace the location of (v,u) from (u,v) and remove them at constant time, and now processing only on the edges in that intersection i'm looking for in asymptotically the same amount of memory used and with more time efficiency.
//====================
ADDITION 3:
Correcting one thing in ADDITION 2 above:
what i wrote in that addition may take more-- not less time than the algorithm without it:
removing the links in the linked lists at Adj[u] and Adj[x], and the corresponding EDGES entry, the direct-memory look-ups during all these isn't much likely to take less CPU cycles than that of relaxing the edges in the algorithm as is.
It still checks every edge (u,v) exactly once and not twice-- once for (u,v) and once for (v,u), and clearly in the same asymptotic time as the algorithm without it. But for little gain in the absolute processing time and with more cost on memory used.
Another alternative is: adding a line of something like
if (v \in S) then continue;
as the first of the for loop. this can be implemented by maintaining S as an array of S[|V|] of boolean and setting its values accordingly as each vertex is added to set S-- which is basically what javier is saying in his ans.
