Java Bellman-Ford 알고리즘 원리 및 구현 방법-java지도 시간-php.cn

Java Bellman-Ford 알고리즘 원리 및 구현 방법

王林

풀어 주다： 2023-05-18 23:58:38

앞으로

1580명이 탐색했습니다.

원 포인트

음수 가중치 간선이 발생하고 음수 루프가 없는 경우(루프 가중치의 합이 음수임) Bellman-Ford 알고리즘을 사용하여 최단 경로를 해결할 수 있습니다. 이 알고리즘의 장점은 음수 변수 가중치의 경우를 처리할 수 있고 구현이 간단하다는 점이지만, 시간 복잡도가 너무 높다는 단점이 있습니다. 그러나 알고리즘은 효율성을 향상시키기 위해 여러 가지 최적화를 거칠 수 있습니다.

Bellman-Ford 알고리즘은 Dijkstra 알고리즘과 유사하지만 둘 다 완화 작업을 기반으로 합니다. Dijkstra 알고리즘은 그리디(greedy) 방법을 사용하여 가장 작은 가중치를 갖는 처리되지 않은 노드를 선택한 다음 이를 완화하는 반면 Bellman-Ford 알고리즘은 모든 가장자리를 총 n-1회 완화합니다. n번째 작업이 여전히 완화될 수 있다면 음의 루프가 있어야 합니다. 왜냐하면 음의 루프는 최단 경로의 길이를 지속적으로 줄일 수 있기 때문입니다. 노드 수는 n이고 간선 수는 m이므로 Bellman-Ford 알고리즘의 최대 실행 시간은 O(nm)입니다.

두 번째 알고리즘 단계

1 데이터 구조

Edge는 완화를 위해 사용해야 하므로 Edge Set Array Storage를 사용합니다. 각 모서리에는 세 개의 도메인이 있습니다. 두 개의 끝점 a와 b, 모든 모서리 j(a,b,w)에 대한 모서리 가중치 w

2 완화 연산

, if dis[e[j]b]> j].a]+e[j].w이면 완화되고 dis[e[j]b]=dis[e[j].a]+e[j].w입니다. 그 중 dis[v]는 소스 포인트에서 노드 v까지의 최단 경로 길이를 나타냅니다.

3 완화 작업을 n-1회 반복합니다.

4 부정적인 루프 판단

완화 작업을 다시 수행합니다. 여전히 완화될 수 있으면 올바른 부정적인 루프가 있음을 의미합니다.

3가지 알고리즘 구현

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

로그인 후 복사