fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Graph{
  5. 	public:
  6. 	int n, m;
  7.  
  8. 	vector<vector<int>> adj;
  9. 	vector<vector<int>> W;
  10. 	vector<vector<int>> predecessor;
  11.  
  12. 	Graph(int nodes): adj(nodes), W(nodes, vector<int>(nodes, INT_MAX)), 
  13. 						predecessor(nodes, vector<int>(nodes, -1)){
  14. 		n = nodes;
  15. 		m = 0;
  16.  
  17. 		for(int i=0; i<n; ++i)
  18. 			W[i][i] = 0;
  19. 	}
  20.  
  21. 	void addEdge(int u, int v, int weight){
  22. 		if(u >= n || v >=n || u < 0 || v < 0){ 
  23. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  24. 			return;
  25. 		}
  26.  
  27. 		W[u][v] = weight;
  28. 		predecessor[u][v] = u;
  29.  
  30. 		adj[u].push_back(v);
  31.  
  32. 		++m;
  33. 	}
  34.  
  35. 	void allPairsShortestPath(){
  36.  
  37. 		for(int k = 0; k < n; ++k){
  38. 			for(int i = 0; i < n; ++i){
  39. 				for(int j = 0; j < n; ++j){
  40. 					if(W[i][k] != INT_MAX && W[k][j] != INT_MAX && W[i][k] + W[k][j] < W[i][j]){
  41. 						W[i][j] = W[i][k] + W[k][j];
  42. 						predecessor[i][j] = k;
  43. 					}
  44. 				}
  45. 			}
  46.  
  47. 			// for(auto row: W){
  48. 			// 	cout<<"|\t";
  49. 			// 	for(auto col: row){
  50. 			// 		cout<<col<<"\t|\t";
  51. 			// 	}
  52. 			// 	cout<<"\n";
  53. 			// }
  54. 			// cout<<"-------------------------------\n";
  55. 		}
  56.  
  57. 		cout<<"Final distance matrix(with rows/cols indexed [0-"<<n-1<<"]):\n";
  58. 		for(auto row: W){
  59. 			cout<<"|\t";
  60. 			for(auto col: row){
  61. 				cout<<col<<"\t|\t";
  62. 			}
  63. 			cout<<"\n";
  64. 		}
  65.  
  66. 		cout<<"-------------------------------\n"
  67. 		"Predecessor matrix(with rows/cols indexed [0-"<<n-1<<"]):\n";
  68. 		for(auto row: predecessor){
  69. 			cout<<"|\t";
  70. 			for(auto col: row){
  71. 				cout<<col<<"\t|\t";
  72. 			}
  73. 			cout<<"\n";
  74. 		}	
  75.  
  76. 		// cout<<"The shortest paths from given source "<<src<<" to\nall other nodes are,\n";
  77.  
  78. 		// 	for(int u = 0; u < n; ++u){
  79. 		// 		if(u != src){
  80. 		// 			cout<<"----------------------------------------\n";
  81. 		// 			if(shortestPaths[u] < INT_MAX){
  82. 		// 				cout<<"Path length: "<<shortestPaths[u]<<" | Path: ";
  83. 		// 				printPath(predecessors, u);
  84. 		// 				cout<<"\n";
  85. 		// 			}
  86. 		// 			else{
  87. 		// 				cout<<"No path exits from given source "<<src<<" to "<<u<<"\n";
  88. 		// 			}
  89. 		// 		}
  90. 		// 	}
  91.  
  92. 	}
  93.  
  94. 	void printGraph(){ 
  95.  
  96. 		if(!m){ 
  97. 			cout<<"The graph is empty!!\n";
  98. 			return;
  99. 		} 
  100.  
  101. 		cout<<"Total # edges in the graph: "<<m<<"\n";
  102.  
  103. 		for(int i = 0; i < n; ++i){ 
  104. 			cout<<"The edges from vertex "<<i<<":";
  105.  
  106. 			for(auto val: adj[i])  
  107. 				cout<<"->"<<val;
  108.  
  109. 			cout<<"\n"; 
  110. 		}
  111. 		cout<<"======================================================\n";
  112. 	}
  113.  
  114. 	void printPath(vector<int> &predecessors, int par){
  115. 		if(par == -1)
  116. 			return;
  117.  
  118. 		printPath(predecessors, predecessors[par]);
  119.  
  120. 		cout<<(predecessors[par] == -1 ? "":"->")<<par;
  121. 	}
  122. };
  123.  
  124. int main()
  125. {
  126. 	int n, u, v, w; 
  127. 	cin>>n;
  128.  
  129. 	Graph g(n);
  130.  
  131. 	cin>>n;
  132.  
  133. 	for(int i=0; i < n; ++i){
  134. 		cin>>u>>v>>w;
  135. 		g.addEdge(u,v,w);
  136. 	}
  137.  
  138. 	g.printGraph();
  139.  
  140. 	g.allPairsShortestPath();
  141.  
  142. 	return 0;
  143. }
  144.  
Success #stdin #stdout 0s 4320KB
comments (?)
stdin
copy 
5 9
0 1 3
0 2 8
0 4 -4
1 3 1
1 4 7
2 1 4
3 0 2
3 2 -5
4 3 6
stdout
copy 
Total # edges in the graph: 9
The edges from vertex 0:->1->2->4
The edges from vertex 1:->3->4
The edges from vertex 2:->1
The edges from vertex 3:->0->2
The edges from vertex 4:->3
======================================================
Final distance matrix(with rows/cols indexed [0-4]):
|	0	|	1	|	-3	|	2	|	-4	|	
|	3	|	0	|	-4	|	1	|	-1	|	
|	7	|	4	|	0	|	5	|	3	|	
|	2	|	-1	|	-5	|	0	|	-2	|	
|	8	|	5	|	1	|	6	|	0	|	
-------------------------------
Predecessor matrix(with rows/cols indexed [0-4]):
|	-1	|	4	|	4	|	4	|	0	|	
|	3	|	-1	|	3	|	1	|	3	|	
|	3	|	2	|	-1	|	1	|	3	|	
|	3	|	2	|	3	|	-1	|	0	|	
|	3	|	3	|	3	|	4	|	-1	|
https://ideone.com/6HlfDE
All pairs shortest path using Floyd Warshall algorithm || Time complexity: O(V^3)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!