一、简介
Bellman-Ford算法是由Richard Bellman和Leicester Ford创立的，求解单源最短路径问题的一种算法。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于Dijkstra算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(V*E)。
二、中心思想
对于n个顶点，循环n-1次，每次遍历所有的边，寻找是否有路径可以进行松弛操作（如果A-->C的距离大于A-->B-->C的距离，则说明由A经B到达C的路径比A直接到达C的路径更短，将A-->C的最短距离更新为A-->B-->C的距离，这个更新的过程称为松弛）。
三、算法特征
适用于有向图和无向图：Bellman-Ford算法可以应用于有向图和无向图。对于有向图，它可以求解从源节点到其他节点的最短路径；对于无向图，它可以求解任意两个节点之间的最短路径。
处理负权边：相对于Dijkstra算法而言，Bellman-Ford算法可以处理包含负权边的图。
可检测负环：Bellman-Ford算法可以检测图中是否存在负权环。如果存在从源节点可达的权值总和为负的环路，说明图中存在无限循环的最短路径。可以通过松弛结束后再进行依次循环（循环第n次）是否还能够进行松弛来判定是否存在负环。
时间复杂度较高：Bellman-Ford算法的时间复杂度为$O(V * E)$，其中V是图中顶点的数量，E是图中边的数量。由于需要对每条边进行松弛操作，因此时间复杂度较高。
需要注意的是，由于Bellman-Ford算法的时间复杂度较高，当图中不存在负环时，更多时候我们会选择使用Dijkstra算法或其他更高效的最短路径算法来解决问题。
四、算法实现
private static class Edge {
public int from; //边的起点
public int to; //边的终点
public int value; //边的权值
public Edge(int from, int to, int value) {
this.from = from;
this.to = to;
this.value = value;
}
}
/**
* @param start 起点
* @param end 终点
* @param dist 每个点到起点的距离，初始值为Integer.MAX_VALUE
* @param n 点的个数
* @param list 边集列表
* @return -1:终点不可达, -2:存在负环
*/
public static int Bellman(int start, int end, int[] dist, int n, List<Edge> list) {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0; //起点距离为0
for (int i = 0; i < n - 1; i++) { //循环n-1次
for (Edge edge : list) { //遍历所有边
if (dist[edge.from] != Integer.MAX_VALUE && dist[edge.to] > dist[edge.from] + edge.value) {
dist[edge.to] = dist[edge.from] + edge.value;
//如果该边的起点是可达的，且该边终点到源点的距离大于该边起点到源点的距离加上该边的权值，就进行松弛操作
}
}
}
for (Edge edge : list) {
if (dist[edge.from] != Integer.MAX_VALUE && dist[edge.to] > dist[edge.from] + edge.value) {
return -2; //进行第n次循环，如果还能松弛，说明存在负环
}
}
if (dist[end] == Integer.MAX_VALUE) {
return -1;
}
return dist[end];
}