By Parul Lohia
C++ program for Go Back N ARQ is mainly used in Computer Networks, it uses the Bellman-Ford algorithm to calculate paths.
A router must notify its neighbors of topological changes on a regular basis under the DVR protocol. Recognized as the old ARPANET optimization mechanism in the past and it is also called the Bellman-Ford algorithm. Each router in Bellman-Ford keeps a Distance Vector table with the distances between itself and any and all potential destination nodes, Distances are calculated using a certain measure are calculated utilizing information from the distance vectors of the neighbors.
Algorithm: Inside a routing packet, a router sends its distance vector to each one of its neighbors. Every router receives the first most current distance vector of each of its neighbors and preserves it. When a router recomputed its distance-vector, it does so because It gets a distance-vector from a neighbor that contains different data than that of the previous one. Also, it could be that it learns that a relationship with a neighbor has gone down.
#include <bits/stdc++.h> using namespace std; int Bellman_Ford(int G[100][100] , int V, int E, int edge[100][2]) { int i,u,v,k,distance[100],S,flag=1; for(i=0;i<V;i++) distance[i] = 1000 ; cout<<"\nEnter source : "; cin>>S; distance[S-1]=0; for(i=0;i<V-1;i++){ for(k=0;k<E;k++){ u = edge[k][0]; v = edge[k][1]; if(distance[u]+G[u][v] < distance[v]) distance[v] = distance[u] + G[u][v]; } } for(k=0;k<E;k++){ u = edge[k][0]; v = edge[k][1] ; if(distance[u]+G[u][v] < distance[v]) flag = 0 ; } if(flag) for(i=0;i<V;i++) cout<<"\nDistance from source "<<S<<" to vertex "<<i+1<<" is "<<distance[i]; return flag; } int main() { int V,edge[100][2],G[100][100],i,j,k=0; cout<<"Enter no. of vertices: "; cin>>V; cout<<"Enter graph in matrix form:\n"; for(i=0;i<V;i++) for(j=0;j<V;j++) { cin>>G[i][j]; if(G[i][j]!=0) edge[k][0]=i,edge[k++][1]=j; } if(Bellman_Ford(G,V,k,edge)) cout<<"\nNo negative weight cycle exists\n"; return 0; }
Output:
Submitted by Parul Lohia (lohiaparul)
Download packets of source code on Coders Packet
Comments