• API
• FAQ
• Tools
• Archive
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.

Top