fork download
copy 
  1. import java.io.*;
  2. import java.lang.*;
  3. import java.util.*;
  4.  
  5. class Graph {
  6. 	class Edge {
  7. 		int src, dest, weight;
  8. 		Edge() { src = dest = weight = 0; }
  9. 	};
  10. 	int V, E;
  11. 	Edge edge[];
  12. 	Graph(int v, int e)
  13. 	{
  14. 		V = v;
  15. 		E = e;
  16. 		edge = new Edge[e];
  17. 		for (int i = 0; i < e; ++i)
  18. 			edge[i] = new Edge();
  19. 	}
  20. 	void BellmanFord(Graph graph, int src)
  21. 	{
  22. 		int V = graph.V, E = graph.E;
  23. 		int dist[] = new int[V];
  24. 		for (int i = 0; i < V; ++i)
  25. 			dist[i] = Integer.MAX_VALUE;
  26. 		dist[src] = 0;
  27. 		for (int i = 1; i < V; ++i) {
  28. 			for (int j = 0; j < E; ++j) {
  29. 				int u = graph.edge[j].src;
  30. 				int v = graph.edge[j].dest;
  31. 				int weight = graph.edge[j].weight;
  32. 				if (dist[u] != Integer.MAX_VALUE
  33. 					&& dist[u] + weight < dist[v])
  34. 					dist[v] = dist[u] + weight;
  35. 			}
  36. 		}
  37. 		for (int j = 0; j < E; ++j) {
  38. 			int u = graph.edge[j].src;
  39. 			int v = graph.edge[j].dest;
  40. 			int weight = graph.edge[j].weight;
  41. 			if (dist[u] != Integer.MAX_VALUE
  42. 				&& dist[u] + weight < dist[v]) {
  43. 				System.out.println(
  44. 					"Graph contains negative weight cycle");
  45. 				return;
  46. 			}
  47. 		}
  48. 		printArr(dist, V);
  49. 	}
  50. 	void printArr(int dist[], int V)
  51. 	{
  52. 		System.out.println("Vertex Distance from Source");
  53. 		for (int i = 0; i < V; ++i)
  54. 			System.out.println(i + "\t\t" + dist[i]);
  55. 	}
  56. 	public static void main(String[] args)
  57. 	{
  58. 		int V = 5;
  59. 		int E = 8;
  60.  
  61. 		Graph graph = new Graph(V, E);
  62.  
  63. 		// adding edge 0-1 (or A-B in above dry run)
  64. 		graph.edge[0].src = 0;
  65. 		graph.edge[0].dest = 1;
  66. 		graph.edge[0].weight = -1;
  67.  
  68. 		// adding edge 0-2 (or A-C in above dry run)
  69. 		graph.edge[1].src = 0;
  70. 		graph.edge[1].dest = 2;
  71. 		graph.edge[1].weight = 4;
  72.  
  73. 		// adding edge 1-2 (or B-C in above dry run)
  74. 		graph.edge[2].src = 1;
  75. 		graph.edge[2].dest = 2;
  76. 		graph.edge[2].weight = 3;
  77.  
  78. 		// adding edge 1-3 (or B-D in above dry run)
  79. 		graph.edge[3].src = 1;
  80. 		graph.edge[3].dest = 3;
  81. 		graph.edge[3].weight = 2;
  82.  
  83. 		// adding edge 1-4 (or B-E in above dry run)
  84. 		graph.edge[4].src = 1;
  85. 		graph.edge[4].dest = 4;
  86. 		graph.edge[4].weight = 2;
  87.  
  88. 		// adding edge 3-2 (or D-C in above dry run)
  89. 		graph.edge[5].src = 3;
  90. 		graph.edge[5].dest = 2;
  91. 		graph.edge[5].weight = 5;
  92.  
  93. 		// adding edge 3-1 (or D-B in above dry run)
  94. 		graph.edge[6].src = 3;
  95. 		graph.edge[6].dest = 1;
  96. 		graph.edge[6].weight = 1;
  97.  
  98. 		// adding edge 4-3 (or E-D in above dry run)
  99. 		graph.edge[7].src = 4;
  100. 		graph.edge[7].dest = 3;
  101. 		graph.edge[7].weight = -3;
  102.  
  103. 		graph.BellmanFord(graph, 0);
  104. 	}
  105. }
Success #stdin #stdout 0.13s 41152KB
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/mip6aG
language:
Java (HotSpot 12)
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!