OSPF (Open Short Path First)

How OSPF Routing Protocol Implemented using Dijkastra Algorithm behind the scene.

4 min readOct 4, 2021

This blog is based on OSPF, OSPF stands for Open Shortest Path First Routing Protocol. In which I will be talking about how behind the Scene OSPF(Open Shortest Path First) Routing protocol is implemented using Dijkstra Algorithm.

Let’s start …

Let me tell you first what is Dijkstra Algorithm is and how it works.

What is Graph?

Graphs are data structures used to represent “connections” between pairs of elements.

These elements are called nodes. They represent real-life objects, persons, or entities.
The connections between nodes are called edges.

What is Dijkstra Algorithm?

Dijkstra’s algorithm is one of the types of Greedy Algorithms that enables us to find the shortest path between any two nodes in a graph. In Dijkstra’s Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the “source node”) to all other nodes in the graph, producing a shortest-path tree.

Working of Dijkstra’s Algorithm:-

Dijkstra’s Algorithm basically starts at the node that you choose (the source node) and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
Once the algorithm has found the shortest path between the source node and another node, that node is marked as “visited” and added to the path.
The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.

What is OSPF(Open Shortest Path First)?

OSPF uses a shorted path first algorithm to build and calculate the shortest path to all known destinations. The shortest path is calculated with the use of the Dijkstra algorithm. The algorithm by itself is quite complicated. This is a very high-level, simplified way of looking at the various steps of the algorithm.

Shortest Path First Algorithm

Routing protocols like OSPF calculate the shortest route to a destination through the network based on an algorithm.

⚡ How to find the shortest path in OSPF using Dijkstra’s Algorithm?

Dijkstra’s algorithm is graph traversing algorithm. In computer network we have sender and receiver, sender will send some frame or message to receiver, but by the time receiver could receive the message, there are many parts which the message can take, that is the job of this algorithm. It will find the shortest path traversed to carry the message from sender to receiver.

Consider a network structure given below, the figure contains the nodes between A to H. We need to examine the shortest path, between A to D, where A being the sender and D being the Receiver.

During the first stage, we need to find the shortest node from the neighbor nodes of source node.
During the second stage, we need to look for second shortest path node, which can be a neighbor node of source node or to the node found in the first stage.
During the third stage, the algorithm looks for third shortest path node form the source node. This node can be neighbor of source node or the nearest node found from first stage or second stage.
The process repeated, until all nodes are visited at least once and if all nodes are visited once, then we can find the shortest path form the source node to destination.

The Formula used to compare between two nodes to find minimum value:

Minimum(Destination value, Marked value + node value) where

Destination values are the destination node value,

Marked value is the source node value,

Node value is the weightage of the edge that connects source and destination.

Example:

Let,Destination value = 18 Marked value = 10 Edge weight = 4 Substituting in the formula, we get= Min(18, 10+4)= Min(18, 14)= 14 (since, 14 is smaller than 18)

Dijkstra’s Algorithm Applications

To find the shortest path
In social networking applications
In a telephone network
To find the locations on the map

Thanks for reading , I hope you like the Blog!!!