fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Number of vertices in the adjMatrix
  5. #define N 4
  6.  
  7. // Function to print the transitive closure of graph
  8. void printTransitiveClosure(int cost[N][N])
  9. {
  10. 	for (int v = 0; v < N; v++)
  11. 	{
  12. 		for (int u = 0; u < N; u++)
  13. 		{
  14. 			if (cost[v][u] == INT_MAX)
  15. 				cout << setw(3) << "0";
  16. 			else
  17. 				cout << setw(3) << "1";
  18. 		}
  19. 		cout << endl;
  20. 	}
  21. }
  22.  
  23. // The function runs Floyd-Warshell algorithm and 
  24. // returns transitive closure of the graph
  25. void FloydWarshell(int adjMatrix[][N])
  26. {
  27. 	// cost[] stores shortest-path information
  28. 	int cost[N][N];
  29.  
  30. 	// initialize cost[]
  31. 	for (int v = 0; v < N; v++) 
  32. 	{
  33. 		for (int u = 0; u < N; u++) 
  34. 		{
  35. 			// initally cost would be same as weight 
  36. 			// of the edge
  37. 			cost[v][u] = adjMatrix[v][u];
  38. 		}
  39. 	}
  40.  
  41. 	// Run Floyd-Warshell
  42. 	for (int k = 0; k < N; k++) 
  43. 	{
  44. 		for (int v = 0; v < N; v++) 
  45. 		{
  46. 			for (int u = 0; u < N; u++) 
  47. 			{
  48. 				// If vertex k is on the shortest path from v to u,
  49. 				// then update the value of cost[v][u]
  50. 				if (cost[v][k] != INT_MAX && cost[k][u] != INT_MAX
  51. 					&& cost[v][k] + cost[k][u] < cost[v][u]) 
  52. 				cost[v][u] = cost[v][k] + cost[k][u];
  53. 			}
  54. 		}
  55. 	}
  56.  
  57. 	// Print the transitive closure of graph
  58. 	printTransitiveClosure(cost);
  59. }
  60.  
  61. int main()
  62. {
  63. 	// given adjacency representation of matrix
  64. 	int adjMatrix[N][N] =
  65. 	{ 
  66. 		{ 		0, INT_MAX,      -2, INT_MAX },
  67. 		{ 		4, 		0,  INT_MAX, INT_MAX },
  68. 		{ INT_MAX, INT_MAX, 	  0, INT_MAX },
  69. 		{ INT_MAX, 		-1, INT_MAX, 	   0 } 
  70. 	};
  71.  
  72. 	// Run Floyd Warshell algorithm
  73. 	FloydWarshell(adjMatrix);
  74.  
  75. 	return 0;
  76. }
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/IvbJo6
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!