fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge {
  5. 	int src, dest, weight;
  6. };
  7.  
  8. struct Graph {
  9. 	int V, E;
  10. 	struct Edge* edge;
  11. };
  12.  
  13. struct Graph* createGraph(int V, int E)
  14. {
  15. 	struct Graph* graph = new Graph;
  16. 	graph->V = V;
  17. 	graph->E = E;
  18. 	graph->edge = new Edge[E];
  19. 	return graph;
  20. }
  21.  
  22. void printArr(int dist[], int n)
  23. {
  24. 	printf("Vertex   Distance from Source\n");
  25. 	for (int i = 0; i < n; ++i)
  26. 		printf("%d \t\t %d\n", i, dist[i]);
  27. }
  28.  
  29. void BellmanFord(struct Graph* graph, int src)
  30. {
  31. 	int V = graph->V;
  32. 	int E = graph->E;
  33. 	int dist[V];
  34. 	for (int i = 0; i < V; i++)
  35. 		dist[i] = INT_MAX;
  36. 	dist[src] = 0;
  37. 	for (int i = 1; i <= V - 1; i++) {
  38. 		for (int j = 0; j < E; j++) {
  39. 			int u = graph->edge[j].src;
  40. 			int v = graph->edge[j].dest;
  41. 			int weight = graph->edge[j].weight;
  42. 			if (dist[u] != INT_MAX
  43. 				&& dist[u] + weight < dist[v])
  44. 				dist[v] = dist[u] + weight;
  45. 		}
  46. 	}
  47. 	for (int i = 0; i < E; i++) {
  48. 		int u = graph->edge[i].src;
  49. 		int v = graph->edge[i].dest;
  50. 		int weight = graph->edge[i].weight;
  51. 		if (dist[u] != INT_MAX
  52. 			&& dist[u] + weight < dist[v]) {
  53. 			printf("Graph contains negative weight cycle");
  54. 			return;
  55. 		}
  56. 	}
  57. 	printArr(dist, V);
  58. 	return;
  59. }
  60.  
  61. int main()
  62. {
  63. 	int V = 5;
  64. 	int E = 8;
  65. 	struct Graph* graph = createGraph(V, E);
  66.  
  67. 	// adding edge 0-1 (or A-B in above dry run)
  68. 	graph->edge[0].src = 0;
  69. 	graph->edge[0].dest = 1;
  70. 	graph->edge[0].weight = -1;
  71.  
  72. 	// adding edge 0-2 (or A-C in above dry run)
  73. 	graph->edge[1].src = 0;
  74. 	graph->edge[1].dest = 2;
  75. 	graph->edge[1].weight = 4;
  76.  
  77. 	// adding edge 1-2 (or B-C in above dry run)
  78. 	graph->edge[2].src = 1;
  79. 	graph->edge[2].dest = 2;
  80. 	graph->edge[2].weight = 3;
  81.  
  82. 	// adding edge 1-3 (or B-D in above dry run)
  83. 	graph->edge[3].src = 1;
  84. 	graph->edge[3].dest = 3;
  85. 	graph->edge[3].weight = 2;
  86.  
  87. 	// adding edge 1-4 (or B-E in above dry run)
  88. 	graph->edge[4].src = 1;
  89. 	graph->edge[4].dest = 4;
  90. 	graph->edge[4].weight = 2;
  91.  
  92. 	// adding edge 3-2 (or D-C in above dry run)
  93. 	graph->edge[5].src = 3;
  94. 	graph->edge[5].dest = 2;
  95. 	graph->edge[5].weight = 5;
  96.  
  97. 	// adding edge 3-1 (or D-B in above dry run)
  98. 	graph->edge[6].src = 3;
  99. 	graph->edge[6].dest = 1;
  100. 	graph->edge[6].weight = 1;
  101.  
  102. 	// adding edge 4-3 (or E-D in above dry run)
  103. 	graph->edge[7].src = 4;
  104. 	graph->edge[7].dest = 3;
  105. 	graph->edge[7].weight = -3;
  106.  
  107. 	BellmanFord(graph, 0);
  108. 	return 0;
  109. }
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Vertex   Distance from Source
0 		 0
1 		 -1
2 		 2
3 		 -2
4 		 1
https://ideone.com/yRkKqk
language:
C++ (gcc 8.3)
created:
1 year 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!