[java] 벨만-포드 알고리즘

04 Dec 2023

java

벨만-포드 알고리즘은 그래프에서 최단 경로를 찾는 알고리즘 중 하나입니다. 이 알고리즘은 음수 가중치를 가지는 간선이 있을 때에도 사용할 수 있습니다.

알고리즘 설명

주어진 그래프 G=(V, E)에서 출발점 s에서 다른 정점까지의 최단 경로를 찾는 알고리즘입니다.

모든 정점까지의 거리를 무한대로 초기화하고, 출발점의 거리를 0으로 설정합니다.
다음과 같은 과정을 모든 정점에 대해서 반복합니다.
- 현재 정점을 v라고 하고, 해당 정점의 거리를 d(v)라고 합니다.
- v와 연결된 모든 간선 (v, u)에 대해서 다음을 수행합니다.
  - 새로운 거리 d(u)가 d(v) + weight(v, u) 보다 작을 경우, d(u)를 갱신합니다.
모든 간선에 대해서 한번 더 반복적으로 relaxation 과정을 수행합니다. 이 과정은 음수 사이클을 검출하는 용도입니다.
relaxation을 한번 더 실행한 결과가 변경되는 경우, 음수 사이클이 존재하는 것을 의미합니다.

시간 복잡도

벨만-포드 알고리즘의 시간 복잡도는 O(

)입니다. 이는 모든 간선에 대해서 relaxation 과정을 V-1번 반복해야 하기 때문입니다. 추가적으로 음수 사이클을 검출하기 위해 relaxation을 한번 더 실행해야 할 수도 있습니다.

예시 코드

import java.util.Arrays;

class BellmanFordAlgorithm {
    static class Edge {
        int src, dest, weight;

        Edge() {
            src = dest = weight = 0;
        }
    }

    int V, E;
    Edge edge[];

    BellmanFordAlgorithm(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[e];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    void BellmanFord(BellmanFordAlgorithm graph, int src) {
        int V = graph.V, E = graph.E;
        int dist[] = new int[V];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int i = 1; i < V; ++i) {
            for (int j = 0; j < E; ++j) {
                int u = graph.edge[j].src;
                int v = graph.edge[j].dest;
                int weight = graph.edge[j].weight;
                if (dist[u] + weight < dist[v] && dist[u] != Integer.MAX_VALUE)
                    dist[v] = dist[u] + weight;
            }
        }

        for (int j = 0; j < E; ++j) {
            int u = graph.edge[j].src;
            int v = graph.edge[j].dest;
            int weight = graph.edge[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v])
                System.out.println("음수 사이클이 존재합니다.");
        }
    }

    public static void main(String[] args) {
        int V = 5;
        int E = 8;
        BellmanFordAlgorithm graph = new BellmanFordAlgorithm(V, E);

        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = -1;

        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 4;

        graph.edge[2].src = 1;
        graph.edge[2].dest = 2;
        graph.edge[2].weight = 3;

        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 2;

        graph.edge[4].src = 1;
        graph.edge[4].dest = 4;
        graph.edge[4].weight = 2;

        graph.edge[5].src = 3;
        graph.edge[5].dest = 2;
        graph.edge[5].weight = 5;

        graph.edge[6].src = 3;
        graph.edge[6].dest = 1;
        graph.edge[6].weight = 1;

        graph.edge[7].src = 4;
        graph.edge[7].dest = 3;
        graph.edge[7].weight = -3;

        graph.BellmanFord(graph, 0);
    }
}

결론

벨만-포드 알고리즘은 음수 가중치를 가지는 그래프에서도 사용할 수 있는 최단 경로 알고리즘입니다. 하지만 시간 복잡도가 다른 알고리즘에 비해 크기 때문에, 그래프에 음수 사이클이 존재하는 지 여부를 주의깊게 확인해야 합니다.