fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Number of vertices in the graph
  5. #define N 4
  6.  
  7. // Function to print the transitive closure of graph
  8. void WarshellAlgorithm(bool graph[N][N])
  9. {
  10. 	// cost[][] stores transitive closure of the graph
  11. 	bool cost[N][N];
  12.  
  13. 	// initialize cost[][] matrix
  14. 	for (int v = 0; v < N; v++)
  15. 		for (int u = 0; u < N; u++)
  16. 			// initally cost would be same as weight 
  17. 			// of the edge
  18. 			cost[v][u] = graph[v][u];
  19.  
  20. 	// Run Warshell algorithm
  21. 	for (int k = 0; k < N; k++)
  22. 		for (int v = 0; v < N; v++)
  23. 			for (int u = 0; u < N; u++)
  24. 			{
  25. 				// If vertex k is on the shortest path from v to u,
  26. 				// then update the value of cost[v][u]
  27. 				if (!cost[v][u])
  28. 					cost[v][u] = (cost[v][k] && cost[k][u]);
  29. 			}
  30.  
  31. 	// Print the transitive closure of graph
  32. 	for (int v = 0; v < N; v++)
  33. 	{
  34. 		for (int u = 0; u < N; u++)
  35. 			cout << setw(3) << cost[v][u];
  36.  
  37. 		cout << endl;
  38. 	}
  39. }
  40.  
  41. int main()
  42. {
  43. 	bool graph[N][N] = 
  44. 	{
  45. 		{ 1, 0, 1, 0 },
  46. 		{ 1, 1, 0, 0 },
  47. 		{ 0, 0, 1, 0 },
  48. 		{ 0, 1, 0, 1 }
  49. 	};
  50.  
  51. 	WarshellAlgorithm(graph);
  52.  
  53. 	return 0;
  54. }
  55.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  1  0  1  0
  1  1  1  0
  0  0  1  0
  1  1  1  1
https://ideone.com/2amhxU
language:
C++14 (gcc 8.3)
created:
7 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!