在本教程中，我们将在Java中看到关于Bellman Ford算法。 Bellman Ford Algorithm用于从定向图中从给定的源顶点找到所有顶点的最短距离。
Dijkstra算法还更有效地提供了相同的目的，但Bellman-Ford算法还适用于具有负重边缘的图表。

除此之外，它还检测图中是否存在任何负周期。

输入格式：在第一行中，给定两个空间分隔的整数，即顶点(V)和边缘(e)的数量。
下一步包含三个整数，每个整数表示从第一整数到第二整数的边缘，其重量等于第三整数。
在最后一行中给定表示源的整数。

输出格式：从给定源输出每个顶点的最短距离。

INPUT-1:
5 7
1 2 2
1 5 5
1 3 1
2 4 1
3 3 4
4 1 5
5 2 -6
1OUTPUT-1:
Distance of 1 from source is 0 and path followed is 1
Distance of 2 from source is -1 and path followed is 1->5->2
Distance of 3 from source is 1 and path followed is 1->3
Distance of 4 from source is 0 and path followed is 1->5->2->4
Distance of 5 from source is 5 and path followed is 1->5INPUT-2:
5 7
1 2 2
1 5 5
1 3 1
2 4 1
3 3 4
4 1 -5
5 2 -6
2OUTPUT-2:
Negative Cycle Detected

算法：基本上在该算法中，我们在随机的边缘循环，顶点-1次。
随机集可以是给定图形的所有边缘的任何顺序。

• 对于每个边缘，E(U-> V)，我们检查V的电流距离是否大于U的距离和此边缘的重量，如果是，这意味着我们刚刚找到了更好的路径与前一条路径较小的距离，我们将顶点V的距离从源更新到e +的距离(U-> v)。
• 说我们将要处理的Readges的随机顺序是，{(1,2)，(1,3)，(1,5)，(2,4)，(4,1)，(3,4)，( 5,2)}我们首先需要初始化从源顶点的所有顶点的距离，除了源顶点本身之外的Infinity，因为它是距离自身的0距离。
  我们需要维护一个HashMap，用于存储包含顶点的顶点的节点，从源节点的距离，从源到此顶点的最短距离的路径。

顶点，节点将是表的键值对。
现在，最初我们的HashMap将是这样，顶点 - >(顶点，距离，路径)1 - >(1,0,1)2 - >(2，Infinity，")3 - >(3，Infinity，"") 4 - >(4，Infinity，"")5 - >(5，Infinity，"")

• 现在我们处理这组边缘(V-1)次，即4次，

第一次迭代：

这里距离(x)表示来自源节点的顶点X的最短距离，直至迭代。

边缘(1-> 2)，距离(2)>距离(1)+重量(1,2)，距离(2)将更新为0 + 2 = 2，现在将路径2和顶点2的路径顶点1 +"2"，即1-> 2

边缘(1-> 3)，距离(3)>距离(1)+重量(1,3)，距离(3)将更新为0 + 1 = 1，现在顶点3的路径将是路径顶点1 +"3"，即1-> 3

边缘(1-> 5)，距离(5)>距离(1)+重量(1,5)，距离(5)将更新为0 + 5 = 5，现在将是顶点5的路径顶点1 +"5"，即1-> 5

边缘(2-> 4)，距离(4)>距离(2)+重量(2,4)，距离(4)将更新为2 + 1 = 3，现在将是顶点4的路径顶点2 +"4"，即1-> 2-> 4

边缘(4-> 1)，距离(1)<距离(4)+权重(4,1)，距离(1)不会更新，因此也不会在其路径中更新。
边缘(3-> 4)，距离(4)<距离(3)+权重(3,4)，距离(4)不会更新，因此也不会在其路径中更新。
边缘(5-> 2)，距离(2)>距离(5)+重量(5,2)，距离(2)将更新为5 +( - 6)= -1，目前顶点2的路径将是，顶点1 +"2"的路径，即1-> 5-> 2.

第二次迭代：边缘(1-> 2)，距离(2)=距离(1)+权重(1,2)，距离(2)不会更新，因此也不会在其路径中更新。

边缘(1-> 3)，距离(3)=距离(1)+重量(1,3)，距离(3)不会更新，因此也不会在其路径中更新。

边缘(2-> 4)，距离(4)>距离(2)+权重(2,4)，距离(4)将更新为-1 + 1 = 0，现在将路径4和顶点4的路径顶点2 +"4"，即1-> 5-> 2-> 4

边缘(3-> 4)，距离(4)<距离(3)+权重(3,4)，距离(4)不会更新，因此也不会在其路径中更新。
边缘(5-> 2)，距离(2)=距离(5)+重量(5,2)，距离(2)不会更新，因此也不会在其路径中更新。

第三次迭代：

没有边缘(U-> V)将保持条件距离(v)>距离(u)+重量(v，u)。

第四和(顶点-1)迭代：

没有更新。

• (顶点 - 1)迭代完成后，我们再次遍历相同的列表，检查是否存在负周期。
  在这个非常最后的迭代期间，如果再次在最短距离中有更新，这意味着图中肯定是一个负周期，因此，每个顶点的最短距离无法计算出该图所以我们可以保持循环再次又一次地，在那个负周期中，继续减少我们的距离。因此，我们打印图表包含负周期并从函数返回。

我们可以清楚地疑惑为什么我们需要迭代(顶点1)次，当我们可以在少于(V-1)迭代中的最短距离时。

找出每个顶点的最短距离所需的迭代次数完全取决于我们正在处理我们的边缘的随机顺序。
请记住，我正在强调找出最短的距离计算，在最坏的情况下我们需要迭代(顶点1)次。

让我们看看，如果我们从源节点开始最遥最远(边缘)开始的设置顺序，我们会尝试检查DIST(2)> DIST(5)+重量(2,5)，但尚未计算的正确距离，它仍然是无限的，所以我们什么都不做，现在我们搬到第二个边缘，尚未计算距离的正确距离，所以我们再次做不到，所以在这个迭代结束之后我们将能够更新仅是那些即时邻居源的顶点的距离。

要更清楚地理解这一点，让我们考虑这个线性图表的最糟糕的随机边缘，

• 说出我们将要处理的Readges的随机顺序是，{(1,2)，(2,3)，(3,4)}现在在第一次迭代中，=> for(1,2)，距离(1) >距离(2)+重量(1,2)，因此，距离(2)从无限远更新为5.
  =>对于(2,3)，距离(3)>距离(2)+重量(2,3)，距离(3)现在为5 + 6 = 11.
  =>对于(3,4)，距离(4)>距离(3)+重量(2,3)，距离(3)现在是11 + 7 = 18.

我们看到，从源(1)的所有顶点(2,3,4)的最短距离仅在一次迭代中计算。

• 现在让我们考虑不同的随机顺序的边缘，{(3,4)，(2,3)，(1,2)}

在第一次迭代中，除了源顶点的即时邻居之外，不会看到任何更新，因为在计算顶点4的距离时，尚未计算顶点2的距离。
在计算顶点的情况下也是如此。
在我们知道距离顶点的距离(如果它最小的或者不是最小的)之前，无法计算进一步的顶点的距离。

在第二次迭代中，对于顶点4没有更新，因为尚未计算近顶点3的距离。
因此，随着我们已经计算出来自源顶点的顶点2的距离，将看到更新。

现在在第三和(顶点-1)迭代中，我们终于找到了顶点4的距离，因为现在我们知道从源顶点的顶点3的距离。

• 在那里，我们看到，迭代的数量完全取决于我们处理边缘的随机顺序，而是在最糟糕的随机边缘中，我们需要迭代(v-1)次以完全计算来自给定的所有顶点的最短距离源节点。因此，我们对此问题的答案，为什么我们为顶点的随机边缘进行此过程 - 1次？

迭代次数=(顶点1)+ 1 {用于检测负周期的一个迭代} =顶点，并且每次都处理包含所有边缘的集合。
因此，该算法的最糟糕时间复杂性将是O(v * e)。

package Graphs;
 
import java.util.HashMap;
import java.util.Scanner;
 
public class BellmanFord {
 
	public static class edge {
		int u;
		int v;
 
		public edge(int u, int v) {
			this.u = u;
			this.v = v;
		}
 
		public String toString() {
			return this.u + " " + this.v;
		}
	}
 
	public static class Node {
		int val;
		int dist;
		String path;
 
		public Node(int val, int dist, String path) {
			this.val = val;
			this.dist = dist;
			this.path = path;
		}
 
		public String toString() {
return "Distance of " + this.val + " from source is " + this.dist + " and path followed is " + this.path;
		}
 
	}
 
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int nodes = scn.nextInt();
		int[][] graph = new int[nodes + 1][nodes + 1];
		int numEdges = scn.nextInt();
		for (int edge = 0; edge < numEdges; edge++) {
			int u = scn.nextInt(), v = scn.nextInt(), w = scn.nextInt();
			graph[u][v] = w;
		}
 
		bellmanford(scn.nextInt(), nodes, numEdges, graph);
 
	}
 
public static edge[] getEdges(int numEdges, int[][] graph) {
		edge[] rv = new edge[numEdges];
 
		int idx = 0;
		for (int u = 1; u < graph.length && idx < rv.length; u++) {
		for (int v = 1; v < graph[u].length && idx < rv.length; v++) {
				rv[idx] = new edge(u, v);
				idx = graph[u][v] != 0 ? idx + 1 : idx;
			}
		}
 
		return rv;
 
	}
 
public static void bellmanford(int src, int nodes, int edges, int[][] graph) {
		/*
		 * we use hashmap to store the nodes of every vertex,
		 * (vertex name, node) will be the key, value pair
		 */
		HashMap<Integer, Node> nodesMap = new HashMap<>();
		for (int i = 1; i < graph.length; i++) {
			/*
			 * initialize the shortest distance of the every
			 *  vertex equal to Infinity as for this vertex 
			 *  the shortest distance is yet to be calculated,
			 *  and initialize an empty path. But if the vertex 
			 *  is source vertex itself, then the shortest distance
			 *  for it will be 0 and path will be initialized with 
			 *  vertex name.
			 */
nodesMap.put(i, new Node(i, i == src ? 0 : (int) 1e9 + 1, i == src ? 
                Integer.toString(i) : ""));
		}
 
		/* outer loop will run for vertices - 1 times */
		for (int var = 1; var <= nodes - 1; var++) {
			/* running inner loop on the set of edges returned 
			 * from getEdges function */
			for (edge e : getEdges(edges, graph)) {
				Node u = nodesMap.get(e.u);
				Node v = nodesMap.get(e.v);
 
				/*
				 * the basic condition for updation of shortest
				 * distance of any node as mentioned in the above 
				 * discussion.
				 */
				if (v.dist > u.dist + graph[u.val][v.val]) {
					v.dist = u.dist + graph[u.val][v.val];
					v.path = u.path + "->" + Integer.toString(v.val);
				}
			}
		}
 
		/*
		 * one more loop in the random set of edges to detect if
		 *  there is any negative cycle or not
		 */
		for (edge e : getEdges(edges, graph)) {
			Node u = nodesMap.get(e.u);
			Node v = nodesMap.get(e.v);
 
			/*
			 * if the we still are able to find shorted distance
			 * this simply means that there is a negative cycle
			 * for sure and hence we return from the function as
			 * shortest distance for every vertex from source can
			 * not be found for such graph as we can get even 
			 * shorter distance by looping once again in that
			 * negative cycle.
			 */
			if (v.dist > u.dist + graph[u.val][v.val]) {
				System.out.println("Negative Cycle Detected");
				return;
			}
		}
 
		for (int node : nodesMap.keySet()) {
			System.out.println(nodesMap.get(node));
		}
 
	}
 
}