최적 경로 찾기 #3 - 벨만-포드(Bellman-Ford) 알고리즘

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

벨만포드 알고리즘은 리차드 벨만(Richard Bellman)과 레스터 포드(Lester Ford)에 의해서 개발되었고 그들의 이름을 따서 벨만포드라고 정해진 알고리즘이다. 

벨만포드 알고리즘은 다익스트라 알고리즘과 비슷한 작동 원리를 가지지만 통행 비용에 음수값이 허용된다는 차이점이 있다. 최적 경로를 도출하기 위해 사용하는 노드의 개수가 n개라면 벨만 포드 알고리즘은 총 n-1 개의 노드에 대한 경로를 모두 탐색한다. 즉, 가장 먼 거리에 있는 노드를 제외한 모든 노드에 대한 경로를 탐색한다.

음수 값이 허용되는 이유는 다익스트라 알고리즘 사용할 때 노드의 간선의 가중치가 음수인 순환 경로가 존재할 경우 순환경로에서 벗어나지 못하고 최단 경로 탐색에 실패하게 되기 때문이다. 벨만포드 알고리즘은 이러한 한계를 극복하기 위해 음의 순환 경로 존재 여부를 판단할 수 있도록 개발되었다.

 

 

벨만포드 알고리즘 의사코드

 

 

기본개념

1. 시작 정점(v) 선택, 시작 정점 거리 = 0 설정, 시작 정점을 제외한 모든 정점 거리 무한대 설정

2. 시작 정점과 인접한 정점(1세대) 수집

3. 인접한 정점(1세대)의 최소 비용 계산, 초기값이 무한대이므로 모든 값 갱신

4. 인접한 정점(1세대)과 인접한 정점(2세대) 수집

5. 인접한 정점(1세대)을 기준으로 인접한 정점(2세대)의 최소 비용 계산

6. 최소 비용을 더 이상 갱신할 수 없을 때까지 순회, 최소 비용 갱신이 되지 않는 경우 탐색 종료

7. 도출된 정점별 최소비용을 계산하여 최종 경로 도출

 

 

해당 경로의 그래프를 이용한 코드 구현은 다음과 같다.

 

코드구현

public class SampleCode {

    private final List<Node> nodeList = new ArrayList<>();

    public void bellman(int s){

        //정점(노드)의 개수
        int v = 9;

        //간선의 개수
        int e = nodeList.size();

        //경로 저장 생성
        int[] distribution = new int[v];

        //모든 정점으로의 거리 무한대 설정
        for (int i = 0; i < v; ++i){
            distribution[i] = Integer.MAX_VALUE;
        }

        //시작 정점 거리 0 설정
        distribution[s] = 0;



        //n(정점 개수) - 1 만큼 간선별 가중치 갱신
        for (int i = 1; i < v; i++) {
            for(int j = 0; j < e; j++){
                Node node = nodeList.get(j);
                int source = node.source;
                int target = node.target;
                int weight = node.weigth;

                if(distribution[source] != Integer.MAX_VALUE){ //MAX_VALUE가 아닌 값 = 출발지
                    int next_w = distribution[source] + weight; //현재 노드까지의 가중치 + 인접 정점 가중치

                    if(next_w < distribution[target]){ //인접 정점 가중치가 경로 누적 가중치보다 작으면 갱신
                        distribution[target] = next_w;
                    }
                }
            }
        }

        for(Node node : nodeList){
            int source = node.source;
            int target = node.target;
            int weight = node.weigth;

            if(distribution[source] != Integer.MAX_VALUE && distribution[source] + weight < distribution[target]){
                System.out.println("contains negative w cycle");
                return;
            }
        }

        printPath(distribution);
    }

    private void printPath(int[] distribution) {
        for (int i = 0; i < distribution.length; i++) {
            System.out.println(i + " : " + distribution[i]);
        }
    }

    static class Node {

        int source;
        int target;
        int weigth;

        public Node(int source, int target, int weight){
            this.source = source;
            this.target = target;
            this.weigth = weight;
        }

    }

    private void addEdge(int source, int target, int weight) {
        Node node = new Node(source, target, weight);
        nodeList.add(node);
    }


    public static void main(String[] args) {

        SampleCode sample = new SampleCode();
        
        sample.addEdge(0, 1, 2);
        sample.addEdge(0, 2, 3);
        sample.addEdge(1, 0, 2);
        sample.addEdge(1, 2, 5);
        sample.addEdge(1, 3, 4);
        sample.addEdge(2, 0, 3);
        sample.addEdge(2, 1, 5);
        sample.addEdge(2, 3, 2);
        sample.addEdge(2, 6, 5);
        sample.addEdge(3, 1, 4);
        sample.addEdge(3, 2, 2);
        sample.addEdge(3, 4, 9);
        sample.addEdge(3, 6, 7);
        sample.addEdge(3, 7, 1);
        sample.addEdge(4, 3, 9);
        sample.addEdge(4, 5, 1);
        sample.addEdge(4, 8, 3);
        sample.addEdge(5, 4, 1);
        sample.addEdge(5, 7, 2);
        sample.addEdge(6, 2, 5);
        sample.addEdge(6, 3, 7);
        sample.addEdge(6, 7, 3);
        sample.addEdge(6, 8, 11);
        sample.addEdge(7, 3, 1);
        sample.addEdge(7, 5, 2);
        sample.addEdge(7, 6, 3);
        sample.addEdge(8, 4, 3);
        sample.addEdge(8, 6, 11);

        sample.bellman(0);

    }
}

 

 

Reference.

백아란. "친환경 교통수단의 통행 변화와 에너지 최적 경로 탐색." 국내석사학위논문 경희대학교 대학원, 2019. 서울

서찬희. "선박의 충돌 회피 경로 탐색을 위한 A* 알고리즘 개발." 국내석사학위논문 부산대학교 대학원, 2022. 부산

https://www.programiz.com/dsa/bellman-ford-algorithm