Dark Mode

1,260 views

1 vote

option 2

Dijkstra’s algorithm

Link state protocols, sometimes called *shortest path first* or *distributed database* protocols, are built around a well-known algorithm from graph theory, E. W. Dijkstra's shortest path algorithm, which is is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

0 votes

**Link State Routing(LSR) algorithm after construction of link state packets, new routes are computed using Dijkstra's algorithm.
Each node independently runs an algorithm over the map to determine the shortest path from itself to every other node in the network;
generally some variant of Dijkstra's algorithm is used.**