Dijkstra算法是求单源点的最短路径，但是不能有负权边，如果有负权边我们可以使用 Bellman-Ford 算法。Bellman-Ford 算法可以解决有负权边的问题，但不能有负权回路，它也可以检测是否有负权回路问题。解题思路就是假设有一条边 {begin,end,value} ，如果 dis[begin] + value < dis[end] ，我们可以更新 dis[end] 的值为 dis[begin] + value ，如下图所示。
所以只需要枚举所有的边即可，代码如下。
for (int j = 0; j < edges.length; j++) {// 遍历边。
int begin = edges[j][0];// 边的起点。
int end = edges[j][1];// 边的终点。
int value = edges[j][2];// 边的权值。
if (dis[begin] + value < dis[end])// 松弛。
dis[end] = dis[begin] + value;
}
如果只枚举一遍的话，有可能只会更新和起始点邻接的点（也就是起始点直接指向的点），与起始点没有邻接的点可能没更新。也就是说如果枚举一遍的话，可以更新从起始点通过一条边到达的点，如果枚举两次的话可以更新从起始点通过两条边到达的点 …… 。而在一个含有 n 个点的图中，一个点最多只有 n-1 条边和起始点相连。所以我们只需要枚举 n-1 次即可计算起始点到其他所有点的距离。
Bellman-Ford 算法虽然可以计算带负权边的图，但不能计算有负权回路的图，因为在负权回路中，如果一直转圈的话，值就会一直变小。
如果没有负权回路，最多枚举 n-1 次就可计算出起始点到其他所有点的最短路径，最后在枚举一遍，所有的值都不会再更新。如果有负权回路，最后在枚举一遍的话，有些值还是会更新。所以在计算完之后还需要在枚举一遍判断有没有负权回路，代码如下。
public static void main(String[] args) {
int size = 4;// 顶点个数。
int max = 100;// 最大值默认给100。
int[][] edges = {{0, 1, 9}, {0, 2, 3}, {1, 2, -7}, {2, 3, 5}};// 边集数组。
int start = 0;// 起始点。
int[] dis = new int[size];
Arrays.fill(dis, max);// 默认到起始点给个最大值。
bellMan(edges, size, dis, start);// Bellman-Ford 算法。
for (int i = 0; i < dis.length; i++)// 打印数组dis的值。
System.out.print(dis[i] + ",");
}
static void bellMan(int[][] edges, int n, int[] dis, int start) {
dis[start] = 0;// 起始点到他自己的距离为 0 。
for (int i = 1; i < n; i++) {// 遍历 n-1 次。
for (int j = 0; j < edges.length; j++) {// 遍历边。
int begin = edges[j][0];// 边的起点。
int end = edges[j][1];// 边的终点。
int value = edges[j][2];// 边的权值。
if (dis[begin] + value < dis[end])// 松弛。
dis[end] = dis[begin] + value;
}
}
// 检测是否有负权回路。
for (int i = 0; i < edges.length; ++i)
if (dis[edges[i][0]] + edges[i][2] < dis[edges[i][1]]) {
Arrays.fill(dis, -1);// 有负权边，dis数组值设置无效。
return;// 还能松弛说明有负权回路。
}
}
我们只需要看 bellMan 函数即可，上面的测试数据如下图所示，打印结果是：0,9,2,7,。也就是说如果有负权边，但没有负权回路， bellMan 算法也是可以计算的。
bellMan 算法虽然可以计算含有负权边的图，但时间复杂度还是比较高的 O(ne)， n 是顶点的个数， e 是边的个数。其实我们还可以优化一下，如果在某一次枚举的时候没有顶点被更新，在枚举下去也不会更新了，可以直接终止。
static void bellMan(int[][] edges, int n, int[] dis, int start) {
dis[start] = 0;// 起始点到他自己的距离为 0 。
for (int i = 1; i < n; i++) {// 遍历 n-1 次。
boolean check = true;// 检测是否更新完了。
for (int j = 0; j < edges.length; j++) {// 遍历边。
int begin = edges[j][0];// 边的起点。
int end = edges[j][1];// 边的终点。
int value = edges[j][2];// 边的权值。
if (dis[begin] + value < dis[end]) {
dis[end] = dis[begin] + value;
check = false;// 还可以更新。
}
}
if (check)// 如果更新完了就不在枚举了。
return;
}
// 检测是否有负权回路。
for (int i = 0; i < edges.length; ++i)
if (dis[edges[i][0]] + edges[i][2] < dis[edges[i][1]]) {
Arrays.fill(dis, -1);// 有负权边，dis数组值设置无效。
return;// 还能松弛说明有负权回路。
}
}联系客服
