快捷導(dǎo)航

詳解Java Bellman-Ford算法原理及實現(xiàn)

更新時間：2022年07月09日 15:51:42 作者：chengqiuming

Bellman-Ford算法與Dijkstra算法類似，都是以松弛操作作為基礎(chǔ)，Bellman-Ford算法是對所有邊都進(jìn)行松弛操作，本文將詳解Bellman-Ford算法原理及實現(xiàn)，感興趣的可以了解一下

一點睛

如果遇到負(fù)權(quán)邊，則在沒有負(fù)環(huán)（回路的權(quán)值之和為負(fù)）存在時，可以采用 Bellman-Ford 算法求解最短路徑。該算法的優(yōu)點是變的權(quán)值可以是負(fù)數(shù)、實現(xiàn)簡單，缺點是時間復(fù)雜度過高。但是該算法可以進(jìn)行若干種優(yōu)化，以提高效率。

Bellman-Ford 算法與 Dijkstra 算法類似，都是以松弛操作作為基礎(chǔ)。Dijkstra 算法以貪心法選取未被處理的具有最小權(quán)值的節(jié)點，然后對其進(jìn)行松弛操作；而 Bellman-Ford 算法對所有邊都進(jìn)行松弛操作，共 n-1 次。因為負(fù)環(huán)可以無限制地減少最短路徑長度，所以吐過發(fā)現(xiàn)第 n 次操作仍然可松弛，則一定存在負(fù)環(huán)。Bellman-Ford 算法最長運行時間為O(nm),其中 n 和 m 分別是節(jié)點數(shù)和邊數(shù)。

二算法步驟

1 數(shù)據(jù)結(jié)構(gòu)

因為需要利用邊進(jìn)行松弛，因此采用邊集數(shù)組存儲。每條邊都有三個域：兩個端點a和b，以及邊權(quán)w

2 松弛操作

對所有的邊 j(a,b,w),如果 dis[e[j]b]>dis[e[j].a]+e[j].w,則松弛，另 dis[e[j]b]=dis[e[j].a]+e[j].w。其中，dis[v] 表示從源點到節(jié)點 v 的最短路徑長度。

3 重復(fù)松弛操作 n-1 次

4 負(fù)環(huán)判斷

再執(zhí)行一次松弛操作，如果仍然可以松弛，則說明右負(fù)環(huán)。

三算法實現(xiàn)

package graph.bellmanford;
 
import java.util.Scanner;
 
public class BellmanFord {
    static node e[] = new node[210];
    static int dis[] = new int[110];
    static int n;
    static int m;
    static int cnt = 0;
 
    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
    }
 
    static void add(int a, int b, int w) {
        e[cnt].a = a;
        e[cnt].b = b;
        e[cnt++].w = w;
    }
 
    static boolean bellman_ford(int u) { // 求源點 u 到其它頂點的最短路徑長度，判負(fù)環(huán)
        for (int i = 0; i < dis.length; i++) {
            dis[i] = 0x3f;
        }
        dis[u] = 0;
        for (int i = 1; i < n; i++) { // 執(zhí)行 n-1 次
            boolean flag = false;
            for (int j = 0; j < m; j++) // 邊數(shù) m 或 cnt
                if (dis[e[j].b] > dis[e[j].a] + e[j].w) {
                    dis[e[j].b] = dis[e[j].a] + e[j].w;
                    flag = true;
                }
            if (!flag)
                return false;
        }
        for (int j = 0; j < m; j++) // 再執(zhí)行 1 次，還能松弛說明有環(huán)
            if (dis[e[j].b] > dis[e[j].a] + e[j].w)
                return true;
        return false;
    }
 
 
    static void print() { // 輸出源點到其它節(jié)點的最短距離
        System.out.println("最短距離：");
        for (int i = 1; i <= n; i++)
            System.out.print(dis[i] + " ");
        System.out.println();
    }
 
    public static void main(String[] args) {
        int a, b, w;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            a = scanner.nextInt();
            b = scanner.nextInt();
            w = scanner.nextInt();
            add(a, b, w);
        }
        if (bellman_ford(1)) // 判斷負(fù)環(huán)
            System.out.println("有負(fù)環(huán)！");
        else
            print();
    }
}
 
class node {
    int a;
    int b;
    int w;
}