SHARE
TWEET

Untitled

a guest May 20th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Distance Vector Routing
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct Edge
  6. {
  7.     int src, dest, weight;
  8. };
  9.  
  10. struct Graph
  11. {
  12.     int V, E;
  13.  
  14.     struct Edge* edge;
  15. };
  16.  
  17. struct Graph* createGraph(int V, int E)
  18. {
  19.     struct Graph* graph = new Graph;
  20.     graph->V = V;
  21.     graph->E = E;
  22.     graph->edge = new Edge[E];
  23.     return graph;
  24. }
  25.  
  26. void printArr(int dist[], int n, int src)
  27. {
  28.     cout<<endl;
  29.     cout<<"__________________________________"<<endl;
  30.     cout<<"Routing Table for "<<src<<endl;
  31.     cout<<"__________________________________"<<endl;;
  32.     for (int i = 0; i < n; ++i)
  33.     {
  34.         if(i == src)
  35.             continue;
  36.         cout<<"Distance to router "<<i<<" --> "<<dist[i]<<endl;
  37.     }
  38.     cout<<"__________________________________"<<endl;;
  39.     cout<<endl;
  40. }
  41.  
  42. void BellmanFord(struct Graph* graph, int src)
  43. {
  44.     int V = graph->V;
  45.     int E = graph->E;
  46.     int dist[V];
  47.  
  48.     for (int i = 0; i < V; i++)
  49.         dist[i]   = INT_MAX;
  50.     dist[src] = 0;
  51.  
  52.     for (int i = 1; i <= V-1; i++)
  53.     {
  54.         for (int j = 0; j < E; j++)
  55.         {
  56.             int u = graph->edge[j].src;
  57.             int v = graph->edge[j].dest;
  58.             int weight = graph->edge[j].weight;
  59.             if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
  60.                 dist[v] = dist[u] + weight;
  61.         }
  62.     }
  63.  
  64.     for (int i = 0; i < E; i++)
  65.     {
  66.         int u = graph->edge[i].src;
  67.         int v = graph->edge[i].dest;
  68.         int weight = graph->edge[i].weight;
  69.         if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
  70.             printf("Graph contains negative weight cycle");
  71.     }
  72.  
  73.     printArr(dist, V, src);
  74.  
  75.     return;
  76. }
  77.  
  78. int main()
  79. {
  80.     int V;
  81.     int E;
  82.     cout<<"Enter number of vertices ";
  83.     cin>>V;
  84.     cout<<"Enter number of edges ";
  85.     cin>>E;
  86.     struct Graph* graph = createGraph(V, 2*E);
  87.  
  88.     for(int i = 0;i<2*E;i+=2)
  89.     {
  90.         cout<<"Enter source, destination and weight"<<endl;
  91.         int src, dest, weight;
  92.         cin>>src>>dest>>weight;
  93.         graph->edge[i].src = src;
  94.         graph->edge[i].dest = dest;
  95.         graph->edge[i].weight = weight;
  96.         graph->edge[i+1].src = dest;
  97.         graph->edge[i+1].dest = src;
  98.         graph->edge[i+1].weight = weight;
  99.  
  100.     }
  101.     for(int i = 0;i<V;i++)
  102.         BellmanFord(graph, i);
  103.  
  104.     return 0;
  105. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top