[Algorithm] Bellman-Ford Algorithm (벨만 포드 알고리즘)

1. Bellman-Ford Algorithm

 

벨만 포드 알고리즘은 다익스트라 알고리즘과 같이 한 정점으로부터 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다.

다익스트라 알고리즘과의 차이점은 음수 가중치를 가진 간선이 그래프에 존재해도 적용이 가능하다는 점이다. 그러나 음수 간선이 사이클을 이루는 경우에는 최단 거리를 찾을 수 없기 때문에 동작하지 않는다.

 

벨만 포드 알고리즘은 두 경로 사이의 최단 경로를 구할 때 모든 간선을 대상으로 edge relaxation을 수행한다. edge relaxation은 두 경로 사이에 더 가까운 경로가 있다면 해당 경로의 거리로 간선을 경감하는 작업이다.

 

그래프에서 s, u 두 정점 사이의 최단 거리 경로는 s -> u로의 바로 연결되는 간선을 통한 경로일 수도 있고, 다른 정점을 중간에 거친 경로일 수도 있다. 벨만 포드 알고리즘은 모든 간선에 대한 edge relaxation을 도착점을 제외한 정점의 개수 V-1 만큼 수행하여 어떤 경로가 최단 거리가 되는지 찾는다.

 

 

2. 벨만 포드 알고리즘

 

1) 출발점으로 부터 최단 거리를 저장할 공간을 선언한다.

2) 출발점은 0으로, 나머지 정점은 무한대로 거리의 값을 초기화한다.

3) 모든 edge에 대해서 edge relaxation을 수행한다.

4) 만약 edge(u, v)에 대해서 현재 u까지의 거리와 edge(u, v)를 더한 값이 현재 v의 최단 거리보다 짧다면 v의 최단거리를 u까지의 최단거리 + edge(u, v)의 값으로 변경한다.

5) 3) ~ 4)를 V-1 만큼 반복한다.

6) 전체 edge를 반복하면서 최단거리의 업데이트가 필요한 경우가 있는지 확인한다.

7) 만약 현재까지의 각 정점들에 대한 최단거리보다 더 짧은 거리가 존재하는 경우 negative cycle이 발생한 것이기 때문에 이에대한 처리를 수행한다.

 

    private int[] bellmanFord(int src) {
        // 최단 거리 초기화
        int[] shortest = new int[N];
        for(int i = 0; i < N; i++) shortest[i] = Integer.MAX_VALUE;
        shortest[src] = 0;

        // 모든 간선에 대해서 N-1번 만큼 edge relaxation 한다.
        for(int i = 1; i < N; i++) {
            for(int j = 0; j < E; j++) {
                Edge edge = this.edges.get(j); // 간선 하나를 가져와서 edge relaxation을 수행한다.
                int u = edge.src;
                int v = edge.dest;
                int w = edge.weight;
                if(shortest[u] != Integer.MAX_VALUE && shortest[u] + w < shortest[v])
                    shortest[v] = shortest[u] + w;
            }
        }

        // negative-wegith cycle의 존재 유무를 확인한다.
        for(int i = 0; i < E; i++) {
            Edge edge = edges.get(i);
            int u = edge.src;
            int v = edge.dest;
            int w = edge.weight;
            // V-1 만큼 반복하여 모든 정점을 고려한 최단 거리를 찾았음에도 더 짧은 경로가 있다는 것은 음수의 사이클이 존재한다는 의미이다.
            if(shortest[u] != Integer.MAX_VALUE && shortest[u] + w < shortest[v]) {
                System.out.println("Graph contains negative weight cycle.");
                return new int[N];
            }
        }

        return shortest;
    }

- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Graph/BellmanFord/BellmanFord.java

 

 

3. 시간 복잡도

 

벨만 포드 알고리즘은 정점의 개수 (V-1)만큼 반복하면서 모든 간선의 edge relaxation을 수행한다.

그렇기 때문에 V * E (모든 간선의 개수)로 O(VE)의 시간 복잡도를 가진다.

 

 

[reference]

- https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/

Bellman–Ford Algorithm | DP-23 - GeeksforGeeks

- https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

벨만-포드 알고리즘 · ratsgo's blog