How is OSPF Routing Protocol implemented using Dijkstra’s Algorithm

Content of this Blog

About OSPF(Open Shortest Path First) Routing Protocol

OSPF routing protocol is a Link State protocol based on cost rather than hops or ticks i.e., it is not vector based routing protocol.

It is an Interior Gateway Protocol for the Internet which is used to distribute IP routing information throughout a single Autonomous System (AS) in an IP network.

Note:

About Dijkstra’s Algorithm

Edsger Dijkstra

Dijkstra’s algorithm was published in 1959 and named after it’s discoverer Edsger Dijkstra, who was a Dutch computer scientist. It aims to find the shortest-path in a directed or undirected graph with non-negative edge weights.

This algorithm predominantly follows Greedy approach for finding locally optimal solution, whereas for building globally optimal solutions, it uses Dynamic Programming approach.

Main logic of this algorithm is based on the following formula:-

dist[r]=min(dist[r], dist[q]+cost[q][r])

Algorithm

Complexity

Implementation of OSPF using Dijkstra’s Algorithm

Java Code for implementation of Dijkstra’s Algorithm in OSPF

Source: