Revision as of 01:23, 24 January 2005 edit Naddy (talk \| contribs) Extended confirmed users 11,363 edits m typos ← Previous edit		Revision as of 01:27, 24 January 2005 edit undo Naddy (talk \| contribs) Extended confirmed users 11,363 edits m →Calculating the shortest paths: typo Next edit →
Line 62: ===Calculating the shortest paths=== Each node ~~indepdently~~independently runs an [[algorithm]] over the map to determine the [[Shortest_path_problem\|shortest path]] from themselves to every other node in the network; generally some variant of [[Dijkstra's algorithm]] is used. Basically, 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 algorithm then repetitively:

Link-state routing protocol: Difference between revisions