Editing Link-state routing protocol (section)

==Calculating the routing table==
The second main stage in the link-state algorithm is to produce routing tables by inspecting the maps. Each node independently runs an [[algorithm]] over the map to determine the [[Shortest path problem|shortest path]] from itself to every other node in the network; generally, some variant of [[Dijkstra's algorithm]] is used. A node maintains two data structures: a [[Tree data structure|tree]] containing nodes which are "done", and a list of ''candidates''. The algorithm starts with both structures empty; it then adds to the first one the node itself. The variant of a [[greedy algorithm]] then repetitively does the following:

* All neighbour nodes which are directly connected to the node are just added to the tree (excepting any nodes which are already in either the tree or the ''candidate'' list). The rest are added to the second (''candidate'') list.
* Each node in the ''candidate'' list is compared to each of the nodes already in the tree. The candidate node which is closest to any of the nodes already in the tree is itself moved into the tree and attached to the appropriate neighbor node. When a node is moved from the candidate list into the tree, it is removed from the candidate list and is not considered in subsequent iterations of the algorithm.

The two steps are repeated as long as there are any nodes left in the candidate list. (When there are none, all the nodes in the network will have been added to the tree.) This procedure ends with the tree containing all the nodes in the network. For any given destination node, the best path for that destination is the node which is the first step from the root node, down the branch in the shortest-path tree which leads toward the desired destination node.