Computer network: LAB 2
Name: Prem Ahirrao
Roll no: 06
PRN: 12311944
PROBLEM STATEMENT
Write a program to find the shortest path using Dijkstra Equation for Link State Routing
Protocol which
is used by Open Shortest Path First Protocol (OSPF) in the Internet for the network flow
provided by
instructor.
Theory:
The Link State Routing Protocol is a type of routing protocol used in computer networks to
determine
the shortest path from one node to another. It is based on the concept of each router or
node in the
network maintaining a database of its neighbors and the cost or distance to reach them.
Dijkstra's
algorithm is commonly employed to compute the shortest path in Link State Routing
Protocol. Below is
a write-up explaining how Dijkstra's algorithm is used to find the shortest path in a network.
Overview of Dijkstra's Algorithm:
Dijkstra's algorithm is a graph search algorithm that efficiently finds the shortest path from a
source
node to all other nodes in a weighted graph. It starts by initializing distances to all nodes as
infinity,
except for the source node, which is set to zero. Then, it iteratively selects the node with the
smallest
distance from the source and updates the distances to its neighboring nodes. The process
continues until
all nodes have been visited.
Steps to Find the Shortest Path:
Initialization: Initialize a distance vector for each node, setting the distance to the source
node as zero
and all other distances as infinity. Also, maintain a set of unvisited nodes.
Selecting the Nearest Node: At each iteration, select the node with the smallest distance
from the
source node among the unvisited nodes.
Updating Distances: For the selected node, update the distances to its neighboring nodes
if the distance
through the selected node is shorter than the current distance. This involves comparing the
sum of the
distance to the selected node and the distance from the selected node to its neighbor with
the current
distance to the neighbor.
Marking Visited Nodes: Mark the selected node as visited and remove it from the set of
unvisited
nodes.
Repeat: Repeat steps 2 to 4 until all nodes have been visited.
Shortest Path Tree: Once the algorithm is complete, a shortest path tree is constructed,
with the source
node as the root and edges representing the shortest paths to each node.
Application in Link State Routing Protocol:
In Link State Routing Protocol, each router exchanges information about its directly
connected links
with other routers in the network. This information includes the link cost or distance. Using
this
information, Dijkstra's algorithm is applied at each router to compute the shortest path to all
other
routers in the network.
Conclusion:
Dijkstra's algorithm plays a crucial role in the Link State Routing Protocol by enabling routers
to
compute the shortest paths efficiently. By maintaining a database of network topology
information and
applying Dijkstra's algorithm, routers can make informed routing decisions, leading to
efficient and
reliable communication within the network.
Algorithm:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define INF INT_MAX
// Function to find the vertex with minimum distance
int minDistance(const vector<int>& dist, const vector<bool>& visited,
int V) {
int min = INF, min_index = -1;
for (int v = 0; v < V; v++) {
if (!visited[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
// Dijkstra's Algorithm
void dijkstra(const vector<vector<int>>& graph, int src) {
int V = graph.size();
vector<int> dist(V, INF); // Distance from source
vector<bool> visited(V, false); // Visited set
vector<int> parent(V, -1); // To reconstruct path
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, visited, V);
if (u == -1) break;
visited[u] = true;
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u]
[v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
parent[v] = u;
}
}
}
// Output results
cout << "\nShortest distances from Router " << src << ":\n";
for (int i = 0; i < V; i++) {
cout << "To Router " << i << " = ";
if (dist[i] == INF)
cout << "Unreachable\n";
else
cout << dist[i] << endl;
}
// print paths
cout << "\nPaths from Router " << src << ":\n";
for (int i = 0; i < V; i++) {
if (i == src) continue;
if (dist[i] == INF) {
cout << "No path to Router " << i << endl;
continue;
}
cout << "Path to Router " << i << ": ";
vector<int> path;
for (int v = i; v != -1; v = parent[v])
path.push_back(v);
for (int j = path.size() - 1; j >= 0; j--) {
cout << path[j];
if (j != 0) cout << " -> ";
}
cout << endl;
}
}
int main() {
int V;
cout << "Enter number of routers (nodes): ";
cin >> V;
vector<vector<int>> graph(V, vector<int>(V));
cout << "Enter cost adjacency matrix (0 for self, INF for no direct
link):\n";
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++) {
cin >> graph[i][j];
if (i != j && graph[i][j] == 0)
graph[i][j] = INF;
}
int src;
cout << "Enter source router index (0 to " << V - 1 << "): ";
cin >> src;
dijkstra(graph, src);
return 0;
}
Result:
