It is unfortunate that Dijkstra's algorithm is so commonly referred to in the routing world as the shortest
path first algorithm. After all, the objective of every routing protocol is to calculate shortest paths. It is
also unfortunate that Dijkstra's algorithm is often made to appear more esoteric than it really is; many
writers just can't resist putting it in set theory notation. The clearest description of the algorithm comes E.
W. Dijkstra's original paper. Here it is in his own words, followed by a "translation" for the link state
routing protocol:
Construct [a] tree of minimum total length between the n nodes. (The tree is a graph with one and only
one 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 choosing 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 1 and repeat the process until sets II and B are empty. The branches in set I form
the tree required.[13]
[13] E. W. Dijkstra. "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
Adapting the algorithm for routers, first note that Dijkstra describes three sets of branches: I, II, and III. In
the router, three databases represent the three sets:
The Tree Database.
This database represents set I. Links (branches) are added to the shortest path tree by adding them
here. When the algorithm is finished, this database will describe the shortest path tree.
The Candidate Database.
This database corresponds to set II. Links are copied from the link state database to this list in a
prescribed order, where they become candidates to be added to the tree.
The Link State Database.
The repository of all links, as has been previously described. This topological database
corresponds to set III.
Dijkstra also specifies two sets of nodes, set A and set B. Here the nodes are routers. Specifically, they are
the routers represented by Neighbor ID in the Router Links triples (Router ID, Neighbor ID, Cost). Set A
comprises the routers connected by the links in the Tree database. Set B is all other routers. Since the
whole point is to find a shortest path to every router, set B should be empty when the algorithm is
finished.
Here's a version of Dijkstra's algorithm adapted for routers:
1. A router initializes the Tree database by adding itself as the root. This entry shows the router as its
own neighbor, with a cost of 0.
2. All triples in the link state database describing links to the root router's neighbors are added to the
Candidate database.
3. The cost from the root to each link in the Candidate database is calculated. The link in the
Candidate database with the lowest cost is moved to the Tree database. If two or more links are an
equally low cost from the root, choose one.
4. The Neighbor ID of the link just added to the Tree database is examined. With the exception of
any triples whose Neighbor ID is already in the Tree database, triples in the link state database
describing that router's neighbors are added to the Candidate database.
5. If entries remain in the Candidate database, return to step 3. If the Candidate database is empty,
then terminate the algorithm. At termination, a single Neighbor ID entry in the Tree database
should represent every router, and the shortest path tree is complete.
Table 4.3 summarizes the process and results of applying Dijkstra's algorithm to build a shortest path tree
for the network in Figure 4.11. Router RA from Figure 4.11 is running the algorithm, using the link state
database of Table 4.2. Figure 4.12 shows the shortest path tree constructed for router RA by this
algorithm. After each router calculates its own tree, it can examine the other routers' network link