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

벨만-포드 알고리즘은 이전에 한 다익스트라 알고리즘처럼 단일 시작점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다.

이 알고리즘은 다익스트라와 달리 가중치가 음수인 간선을 포함하는 그래프에서 최단 경로를 정확히 구할 수 있고, 음수인 사이클을 판별해낼 수 있습니다. 다익스트라 알고리즘에 비해 시간복잡도가 좋지 않으므로, 음수인 간선을 갖는 그래프나 음수인 사이클을 판별할 때 사용하는 것이 좋습니다.

 

# 완화 (Relaxation)

이 알고리즘의 가장 핵심이 되는 특성입니다. u에서 v까지의 최단거리 dis[v] <= dis[u] + u에서 v 간선의 가중치가 항상 참이라는 것입니다. 사실 이 완화과정은 이미 다익스트라 알고리즘에서도 했었는데, 해당 노드에서 인접한 노드에 방문할 때 dis[nextNode.v] > cur.weight + nextNode.weight이 만족할 경우에만 우선순위 큐에 넣었습니다. 

for (Node nextNode : graph.sparseList.get(current.v)) {
                int newDis = current.weight + nextNode.weight;
 
                if (dis[nextNode.v] > newDis) {
                    dis[nextNode.v] = newDis;
                }
}

즉, 다음에 방문할 v까지의 최단거리는 u까지 오는 최단거리에서 u에서 v를 가는데 필요한 비용보다 같거나 작다라는 말입니다. 다익스트라 알고리즘에서도 다음에 방문할 v가 더 클 경우 갱신하는 모습을 위에 코드에서 볼 수 있죠.

이렇게 벨만-포드 알고리즘에서는 해당 노드까지 가는 최대 상한값을 가진 upper[]로 시작해서, 모든 간선에 upper[v] > upper[u] + weight가 만족할 때 upper[v] = upper[u] + weight을 하는 완화작업을 반복적으로 실행합니다. 이렇게 되면 upper는 점점 줄어들고 실제 우리가 구하고자하는 최단거리를 구할 수 있게 됩니다.

이제 완화작업을 최대 몇번해야 최단거리를 찾을 수 있을지를 생각해보겠습니다. 음수 사이클이 없는 그래프에서 최단 경로는 한 정점을 두번 이상 지나는 일이 없습니다. 그렇다면 최단 경로는 최대 V개의 정점을 갖게 되고, V-1개의 간선을 갖게 되므로 모든 간선에 대한 완화작업은 최대 V-1번이면 충분합니다.

 

# 소스코드

이 소스코드의 예시 그래프는 이전 다익스트라 포스팅에서 다룬 것과 동일합니다.

그래프 (출발점은 1)

=import java.io.IOException;
import java.util.*;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
        int N = 7;
        Graph graph = new Graph(N);
        graph.addEdge(1, 2, 5);
        graph.addEdge(1, 3, 1);
        graph.addEdge(3, 4, 2);
        graph.addEdge(4, 5, 5);
        graph.addEdge(4, 2, 1);
        graph.addEdge(4, 7, 3);
        graph.addEdge(2, 6, 3);
        graph.addEdge(2, 7, 3);
        graph.addEdge(6, 7, 2);
 
        bellmanFord(graph, N, 1);
    }
 
    private static void bellmanFord(Graph graph, int N, int start) {
        int[] upper = new int[N+1];
        //스패닝 트리를 위한 배열
        int[] parent = new int[N+1];
 
        Arrays.fill(upper, Integer.MAX_VALUE);
        upper[start] = 0;
        parent[start] = start;
 
        boolean isUpdate = false;
 
        //for문의 loop횟수는 N-1번, 1번 더 반복면 음수 사이클이 있는지 확인할 수 있음
        for (int i = 0; i < N-1; i++) {
            isUpdate = false;
            //모든 간선에 대한 완화작업
            for (int cur = 1; cur <= N; cur++) {
                for (Node next : graph.sparseList.get(cur)) {
                    //현재의 노드의 upper가 상한 값이면 갱신 불가능
                    if (upper[cur] != Integer.MAX_VALUE) {
                        int nextCost = upper[cur] + next.weight;
                        if (upper[next.v] > nextCost) {
                            upper[next.v] = nextCost;
 
                            //스패닝 트리에 기록
                            parent[next.v] = cur;
                            isUpdate = true;
                        }
                    }
                }
            }
 
            //모든 간선에 대해 완화가 완료되었으므로 종료
            if (!isUpdate)
                break;
        }
 
        System.out.println(Arrays.toString(upper));
        System.out.println(Arrays.toString(parent));
    }
    private static void findRoot(int v, int start, int[] parent) {
        int finish = v;
        StringBuilder sb = new StringBuilder();
        while (v != start) {
            sb.insert(0, " -> "+v);
            v = parent[v];
        }
        sb.insert(0, start);
 
        System.out.println(finish +" : "+sb.toString());
    }
 
    public static class Node implements Comparable<Node>{
        int v;
        int weight;
        public Node(int v, int weight) {
            this.v = v;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return Integer.compare(weight, o.weight);
        }
    }
 
    public static class Graph {
        int n;
        List<List<Node>> sparseList;
        public Graph(int n) {
            this.n = n;
            this.sparseList = new ArrayList<>();
            for (int i=0; i< n+1; i++)
                sparseList.add(new ArrayList<>());
        }
 
        /**
         * 양쪽으로 연결
         */
        public void addEdge(int u, int v, int w){
            sparseList.get(u).add(new Node(v, w));
            sparseList.get(v).add(new Node(u, w));
        }
 
        //한쪽으로 연결
        public void addEdgeSingle(int u, int v, int w) {
            sparseList.get(u).add(new Node(v, w));
        }
    }
}

 

이 코드의 결과값을 보기 위해 upper 배열을 출력시키면 각 노드까지 가는데 최단거리가 정확히 계산된 것이 보입니다.

물론 이 예시 그래프는 음수인 간선을 포함하고 있지 않지만, 음수인 간선에서도 정확히 작동합니다.

 

 

# 음수인 사이클의 판별

출처 : https://m.blog.naver.com/kks227/220796963742

벨만 포드 알고리즘을 통해 음수인 사이클의 판별할 수 있다고 했습니다. 음수인 사이클의 특징은 위 그래프와 같이 1 -> 2 -> 3까지 가는 가중치의 합이 -2로 0보다 작아 이 사이클을 돌면 돌수록 가중치는 더욱 작아질 것입니다. 그래프에서 이런 사이클이 있는지 판단은 간단합니다. 음수인 사이클이 있으면 매번 완화작업을 시도할 때 항상 한번은 성공을 하게 될 것입니다. 그렇다면 위에서 V-1개의 루프만큼 완화작업을 한 뒤 한번 더인 V번째의 완화작업을 했을 때도 완화는 성공하는 것이죠. 이는 위의 코드에서 단 두줄의 코드 수정이면 충분합니다. 

private static boolean hasNegativeCycle(Graph graph, int N, int start) {
        int[] upper = new int[N+1];
        Arrays.fill(upper, Integer.MAX_VALUE);
        upper[start] = 0;
 
        boolean isUpdate = false;
 
        //for문의 loop횟수는 N번, 1번 더 반복면 음수 사이클이 있는지 확인할 수 있음
        for (int i = 0; i < N; i++) {
            isUpdate = false;
            //모든 간선에 대한 완화작업
            for (int cur = 1; cur <= N; cur++) {
                for (Node next : graph.sparseList.get(cur)) {
                    //현재의 노드의 upper가 상한 값이면 갱신 불가능
                    if (upper[cur] != Integer.MAX_VALUE) {
                        int nextCost = upper[cur] + next.weight;
                        if (upper[next.v] > nextCost) {
                            upper[next.v] = nextCost;
 
                            isUpdate = true;
                        }
                    }
                }
            }
 
            //모든 간선에 대해 완화가 완료되었으므로 종료
            if (!isUpdate)
                break;
        }
        
        //완화작업에 성공했다면 isUpdate는 true를 갖게 되고, 이 말은 음수인 사이클이 있다는 것임 
        return isUpdate;
    }

 

# 시간복잡도

한번의 완화작업은 모든 간선을 살펴보게 되므로 O(E), 이것을 V번 만큼 반복수행하므로, O(VE)라는 시간복잡도를 갖게 됩니다.