Prinsip algoritma Java Bellman-Ford dan kaedah pelaksanaan

Satu mata

Jika anda menghadapi kelebihan berwajaran negatif, dan tiada gelung negatif (jumlah berat gelung adalah negatif), anda boleh menggunakan algoritma Bellman-Ford untuk menyelesaikan laluan terpendek. Kelebihan algoritma ini ialah ia boleh mengendalikan kes pemberat pembolehubah negatif dan mudah untuk dilaksanakan, tetapi kelemahannya ialah kerumitan masa terlalu tinggi. Tetapi algoritma boleh dioptimumkan dalam beberapa cara untuk meningkatkan kecekapan.

Algoritma Bellman-Ford adalah serupa dengan algoritma Dijkstra, kedua-duanya berdasarkan operasi kelonggaran. Algoritma Dijkstra menggunakan kaedah tamak untuk memilih nod yang tidak diproses dengan berat terkecil, dan kemudian melonggarkannya manakala algoritma Bellman-Ford melonggarkan semua tepi sebanyak n-1 kali. Jika operasi ke-n masih boleh berehat, maka mesti ada gelung negatif, kerana gelung negatif boleh terus mengurangkan panjang laluan terpendek. Bilangan nod ialah n dan bilangan tepi ialah m, maka masa berjalan maksimum algoritma Bellman-Ford ialah O(nm).

2 langkah Algoritma

1 Struktur data

Oleh kerana tepi perlu digunakan untuk kelonggaran, storan tatasusunan set tepi digunakan. Setiap tepi mempunyai tiga domain: dua titik akhir a dan b, dan berat tepi w

2 operasi kelonggaran

untuk semua tepi j(a,b,w), jika dis[ e[j] b]>dis[e[j].a]+e[j].w, kemudian dilonggarkan, dan dis[e[j]b]=dis[e[j].a]+e[ j] .w. Antaranya, dis[v] mewakili panjang laluan terpendek dari titik sumber ke nod v.

3 Ulang operasi kelonggaran n-1 kali

4 Penghakiman gelung negatif

Lakukan operasi kelonggaran itu lagi Jika masih boleh dilonggarkan, bermakna ada hak gelung negatif.

Tiga pelaksanaan algoritma

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 到其它顶点的最短路径长度，判负环
        for (int i = 0; i < dis.length; i++) {
            dis[i] = 0x3f;
        }
        dis[u] = 0;
        for (int i = 1; i < n; i++) { // 执行 n-1 次
            boolean flag = false;
            for (int j = 0; j < m; j++) // 边数 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++) // 再执行 1 次，还能松弛说明有环
            if (dis[e[j].b] > dis[e[j].a] + e[j].w)
                return true;
        return false;
    }
 
 
    static void print() { // 输出源点到其它节点的最短距离
        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)) // 判断负环
            System.out.println("有负环！");
        else
            print();
    }
}
 
class node {
    int a;
    int b;
    int w;
}

Empat ujian

1 Ujian tanpa gelung negatif

2 Ujian dengan Ujian gelung negatif

Atas ialah kandungan terperinci Prinsip algoritma Java Bellman-Ford dan kaedah pelaksanaan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!