This is also known as the shortest path first algorithm, but it doesn't take a CCIE to know that calculating the shortest path is the objective of every routing protocol. Ahem.
The following is an excerpt from Dijkstra's original paper, entitled "A Note on Two Problems in Connexion with Graphs."
Construct tree of minimum total length between the n nodes. (The tree is a graph with one and only path between every two nodes.)
In the course of the construction that we present here, the branches are divided into three sets:
I. The branches definitely assigned to the tree under construction (they will be in a subtree);
II. The branches from which the next branch to be added to set I will be selected;
III. The remaining branches (rejected or not considered).
The nodes are divided into two sets:
A. The nodes connected by the branches of set I,
B. The remaining nodes (one and only one branch of set II will lead
to each of these nodes).
We start the construction by doing an arbitrary node as the only
member of set A, and by placing all branches that end in this node in set II. To start with set I is empty. From then onwards we perform the following two steps repeatedly.
Step 1: The shortest branch of set II is removed from this set and added to set I. As a result, one node is transferred from set B to set A.
Step 2: Consider the branches leading from the node, that has just
been transferred to set A, to the nodes that are still in set B. If the branch under construction is longer than the corresponding branch in set II, it is rejected; if it is shorter, it replaces the corresponding branch in set II, and the latter is rejected.
We then return to step I and repeat the process until sets II and B are empty. The branches in set I form the tree required.
E.W Dijkstra. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik, Vol. 1, 1959, pp. 269-271.
So, in a version adapted for routers, three databases represent the three sets of branches (i.e., I, II, and III).
- The Tree Database. Represents set I. Links (branches) are added to the SP tree here.
- The Candidate Database. For set II. Links from the LSDB (see following) are copied here in an order.
- The Link State Database. For set III. All links.
Set A and B would be routers, viz., the routers represented by Neighbor ID: Router, Neighbor, Cost). Set A comprises routers in the Tree DB, and Set B are all others. Se B, then, should be empty when the algorithm is finished.