fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int dmax=1e9+7;
  5.  
  6. struct node
  7. {
  8.     unsigned dist[20];
  9.     unsigned from[20];
  10. }graph[10];
  11.  
  12. struct comp
  13. {
  14. 	bool operator()(const pair<int,int> &a,const pair<int,int> &b)
  15. 	{
  16. 		return (a.second>b.second);
  17. 	}
  18. };
  19.  
  20. int main()
  21. {
  22. 	int ch=1,i,j,k,u,v,w,n,m,src;
  23. 	vector<vector<pair<int,int> > > graph1;
  24. 	vector<pair<pair<int,int>,int> > graph2;
  25. 	if(ch==1) // Dijkstra's algorithm
  26. 	{
  27. 		priority_queue<pair<int,int>,vector<pair<int,int> >,comp> pq;
  28. 		cin>>n>>m;
  29. 		graph1.resize(n);
  30. 		int dist[n];
  31. 		bool vis[n];
  32. 		for(i=1;i<=m;i++)
  33. 		{
  34. 			cin>>u>>v>>w;
  35. 			graph1[u].push_back({v,w});
  36. 			graph1[v].push_back({u,w});
  37. 			graph2.push_back({{u,v},w});
  38. 		}
  39. 		cin>>src;
  40. 		for(i=0;i<n;i++)
  41. 		{
  42. 			dist[i]=dmax;
  43. 			vis[i]=0;
  44. 		}
  45. 		dist[src]=0;
  46. 		pq.push({src,0});
  47. 		while(!pq.empty())
  48. 		{
  49. 			u=pq.top().first;
  50. 			pq.pop();
  51. 			if(vis[u])
  52. 				continue;
  53. 			for(i=0;i<graph1[u].size();i++)
  54. 			{
  55. 				v=graph1[u][i].first;
  56. 				w=graph1[u][i].second;
  57. 				if(!vis[v] && dist[u]+w<dist[v])
  58. 				{
  59. 					dist[v]=dist[u]+w;
  60. 					pq.push({v,dist[v]});
  61. 				}
  62. 			}
  63. 			vis[u]=1;
  64. 		}
  65. 		cout<<"\nDijkstra's algorithm :\n";
  66. 		for(i=0;i<n;i++)
  67. 			cout<<dist[i]<<' ';
  68. 		cout<<endl;
  69. 		ch++;
  70. 	}
  71. 	if(ch==2) // Bellman Ford's algorithm
  72. 	{
  73. 		int dist[1003],flag=1,dmax=1e9+7;
  74. 		for(i=0;i<n;i++)
  75. 			dist[i]=dmax;
  76. 		dist[src]=0;
  77. 		cout<<"\n\nBellman Ford's algorithm :\n\n";
  78. 		for(i=1;i<n;i++)
  79. 		{
  80. 			for(j=0;j<m;j++)
  81. 			{
  82. 				u=graph2[j].first.first;
  83. 				v=graph2[j].first.second;
  84. 				w=graph2[j].second;
  85. 				if(dist[v]>dist[u]+w)
  86. 					dist[v]=dist[u]+w;
  87. 				for(k=0;k<n;k++)
  88. 					cout<<dist[k]<<' ';
  89. 				cout<<endl;
  90. 			}
  91. 		}
  92. 		ch++;
  93. 	}
  94. 	int adjm[20][20],nodes=n,count=0,x,y;
  95. 	int rp[20][20];
  96. 	if(ch==3) // Distance Vector Routing Algorithm
  97. 	{
  98. 		cout<<"Distance Vector Routing algorithm :\n";
  99.     	//printf("\nEnter the adjacency matrix :\n");
  100.     	for(i=0;i<nodes;i++)
  101.     	{
  102.         	for(j=0;j<nodes;j++)
  103.         	{
  104.         		scanf("%d",&adjm[i][j]);
  105.             	if(adjm[i][j]==1000)
  106.             		rp[i][j]=-1;
  107.             	else
  108.             		rp[i][j]=adjm[i][j];
  109.             	adjm[i][i]=0;
  110.             	graph[i].dist[j]=adjm[i][j];
  111.             	graph[i].from[j]=j;
  112.         	}
  113.     	}
  114.     	do
  115.     	{
  116.         	count=0;
  117.         	for(i=0;i<nodes;i++)
  118.         	{
  119.             	for(j=0;j<nodes;j++)
  120.             	{
  121.             		for(k=0;k<nodes;k++)
  122.             		{
  123.                 		if(graph[i].dist[j]>adjm[i][k]+graph[k].dist[j])
  124.                 		{
  125.                     		graph[i].dist[j]=graph[i].dist[k]+graph[k].dist[j];
  126.                     		graph[i].from[j]=k;
  127.                     		count++;
  128.                 		}
  129.             		}
  130.             	}
  131.         	}
  132.     	}while(count!=0);
  133.     	for(i=0;i<nodes;i++)
  134.     	{
  135.     		for(j=0;j<nodes;j++)
  136.     		{
  137.     			x=j;
  138. 				y=graph[i].from[j];
  139. 				while(x!=y)
  140. 				{
  141. 					x=y;
  142. 					y=graph[i].from[x];
  143. 				}
  144. 				graph[i].from[j]=x;
  145.     		}
  146.     	}
  147.     	for(i=0;i<nodes;i++)
  148.     	{
  149.         	printf("\n\nFor router %d\n",i);
  150.         	for(j=0;j<nodes;j++)
  151.             	printf("\t\nNode %d via %d Distance %d ",j,graph[i].from[j],graph[i].dist[j]);
  152.     	}
  153.     	ch++;
  154. 	}
  155. 	if(ch==4) // Linked State Routing algorithm
  156. 	{
  157.     	cout<<"\n\nLinked State Routing algorithm :\n\n";
  158.     	for(i=0;i<nodes;i++)
  159.     	{
  160.         	printf("\n\nFor router %d\n",i);
  161.         	for(j=0;j<nodes;j++)
  162.         	{
  163.     			if(rp[i][j]!=-1)
  164.             		printf("\t\nNode %d via %d Distance %d ",j,graph[i].from[j],graph[i].dist[j]);
  165.         	}
  166.     	}
  167. 	}
  168. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
5 6
0 1 2
0 2 1
0 4 8
1 2 1
1 3 3
3 4 1
0
0 2 1 1000 8
2 0 1 3 1000
1 1 0 1000 1000
1000 3 1000 0 1
8 1000 1000 1 1000
stdout
copy 
Dijkstra's algorithm :
0 2 1 5 6 


Bellman Ford's algorithm :

0 2 1000000007 1000000007 1000000007 
0 2 1 1000000007 1000000007 
0 2 1 1000000007 8 
0 2 1 1000000007 8 
0 2 1 5 8 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
0 2 1 5 6 
Distance Vector Routing algorithm :


For router 0
	
Node 0 via 0 Distance 0 	
Node 1 via 1 Distance 2 	
Node 2 via 2 Distance 1 	
Node 3 via 1 Distance 5 	
Node 4 via 1 Distance 6 

For router 1
	
Node 0 via 0 Distance 2 	
Node 1 via 1 Distance 0 	
Node 2 via 2 Distance 1 	
Node 3 via 3 Distance 3 	
Node 4 via 3 Distance 4 

For router 2
	
Node 0 via 0 Distance 1 	
Node 1 via 1 Distance 1 	
Node 2 via 2 Distance 0 	
Node 3 via 1 Distance 4 	
Node 4 via 1 Distance 5 

For router 3
	
Node 0 via 1 Distance 5 	
Node 1 via 1 Distance 3 	
Node 2 via 1 Distance 4 	
Node 3 via 3 Distance 0 	
Node 4 via 4 Distance 1 

For router 4
	
Node 0 via 3 Distance 6 	
Node 1 via 3 Distance 4 	
Node 2 via 3 Distance 5 	
Node 3 via 3 Distance 1 	
Node 4 via 4 Distance 0 

Linked State Routing algorithm :



For router 0
	
Node 0 via 0 Distance 0 	
Node 1 via 1 Distance 2 	
Node 2 via 2 Distance 1 	
Node 4 via 1 Distance 6 

For router 1
	
Node 0 via 0 Distance 2 	
Node 1 via 1 Distance 0 	
Node 2 via 2 Distance 1 	
Node 3 via 3 Distance 3 

For router 2
	
Node 0 via 0 Distance 1 	
Node 1 via 1 Distance 1 	
Node 2 via 2 Distance 0 

For router 3
	
Node 1 via 1 Distance 3 	
Node 3 via 3 Distance 0 	
Node 4 via 4 Distance 1 

For router 4
	
Node 0 via 3 Distance 6 	
Node 3 via 3 Distance 1
https://ideone.com/WuA3U2
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!