ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘/벨만포드] 벨만-포드(Bellman-Ford) 알고리즘
    Mhwan's Study/Algorithms 2021. 1. 23. 03:12

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

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

     

    # 완화 (Relaxation)

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

    1
    2
    3
    4
    5
    6
    7
    for (Node nextNode : graph.sparseList.get(current.v)) {
                    int newDis = current.weight + nextNode.weight;
     
                    if (dis[nextNode.v] > newDis) {
                        dis[nextNode.v] = newDis;
                    }
    }
    cs

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

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

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

     

    # 소스코드

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

    그래프 (출발점은 1)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    =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(125);
            graph.addEdge(131);
            graph.addEdge(342);
            graph.addEdge(455);
            graph.addEdge(421);
            graph.addEdge(473);
            graph.addEdge(263);
            graph.addEdge(273);
            graph.addEdge(672);
     
            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));
            }
        }
    }
    cs

     

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

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

     

     

    # 음수인 사이클의 판별

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    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;
        }
    cs

     

    # 시간복잡도

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

    댓글

Designed by Mhwan.