Principe de l'algorithme Java Bellman-Ford et méthode de mise en œuvre

Un point

Si vous rencontrez un bord pondéré négativement et qu'il n'y a pas de boucle négative (la somme des poids de la boucle est négative), vous pouvez utiliser l'algorithme de Bellman-Ford pour résoudre le chemin le plus court. L’avantage de cet algorithme est qu’il peut gérer le cas de poids variables négatifs et qu’il est simple à mettre en œuvre, mais son inconvénient est que la complexité temporelle est trop élevée. Mais l'algorithme peut être optimisé de plusieurs manières pour augmenter l'efficacité.

L'algorithme de Bellman-Ford est similaire à l'algorithme de Dijkstra, tous deux basés sur des opérations de relaxation. L'algorithme de Dijkstra utilise une méthode gloutonne pour sélectionner le nœud non traité avec le plus petit poids, puis le relâche tandis que l'algorithme de Bellman-Ford relâche toutes les arêtes un total de n-1 fois ; Si la nième opération peut encore se détendre, alors il doit y avoir une boucle négative, car la boucle négative peut réduire continuellement la longueur du chemin le plus court. Le nombre de nœuds est n et le nombre d'arêtes est m, alors le temps d'exécution maximum de l'algorithme de Bellman-Ford est O (nm).

Deuxièmes étapes de l'algorithme

1 Structure des données

Parce que les bords doivent être utilisés pour la relaxation, le stockage de tableau d'ensembles de bords est utilisé. Chaque arête a trois domaines : deux points d'extrémité a et b et un poids d'arête w

2 Opération de relaxation

pour toutes les arêtes j(a,b,w), si dis[e[j]b]> [j].a]+e[j].w, alors il est détendu, et dis[e[j]b]=dis[e[j].a]+e[j].w. Parmi eux, dis[v] représente le chemin le plus court du point source au nœud v.

3 Répétez l'opération de relaxation n-1 fois

4 Jugement de boucle négative

Effectuez à nouveau l'opération de relaxation Si elle peut encore être relâchée, cela signifie qu'il y a une boucle négative droite.

Mise en œuvre de trois algorithmes

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;
}

Quatre tests

1 Test sans boucle négative

2 Test avec boucle négative

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!