[알고리즘] 벨만포드

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

그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 각각 구하는 알고리즘

음의 가중치를 갖는 간선이 있을 때 사용하는 알고리즘이다.

 

시간복잡도

매번 모든 간선을 확인하기 때문에 O(V*E) 정점 * 간선

 

 

공간복잡도

정점의 개수만큼 배열이 필요하므로 O(V)

 

 

 

다익스트라와의 차이점

 

다익스트라

• 매번 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택
• 음의 가중치가 있으면 사용 X
• 시간 복잡도가 빠르다

벨만포드

• 매번 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구함
• 음의 가중치가 있어도 사용 가능 & 음수 사이클 여부 확인 가능
• 시간 복잡도가 느리다.

 

즉, 간선에 음수가중치가 있으면 벨만포드, 없으면 다익스트라를 사용!

 

 

구현 방식

 

1. 정점의 개수만큼의 길이를 가진 배열 (dist) 을 생성해  시작노드는 0 나머지는 INF로 설정한다.
   • 코드상으로 무한을 표시할 수 없으므로 대개 자료형의 가장 큰 값으로 설정 ex) Integer.MAX_VALUE
2. 모든 간선을 확인해 최단경로 배열을 업데이트한다.
3. 출발노드가 무한대일 경우는 건너뛰고, 도착노드의 최단경로 값 > 출발노드의 최단경로 값 + 두 노드를 잇는 간선의 가중치일 경우 업데이트한다.
4. 모든 간선에 대해 반복하고 마지막으로 한 번 더 반복하여 음수 사이클을 확인한다.
   • 한 정점에서 다른 정점으로 가는 최단거리는 항상 지나가는 정점의 수 - 1의 길이를 갖는다.
   • 따라서 정점의 수 - 1 만큼 실행한 후, 한 번 더 실행했을 때 dist가 업데이트 된다면 음수 사이클이 있다고 할 수 있다.

 

 

예제

 

 

 

예제 코드

 

벨만포드 알고리즘

 

package Path;

import java.util.Arrays;

public class Bellman {

    private static final int INF = Integer.MAX_VALUE;

    public boolean findPath(int v, int[][] edges, int start) {
        // 양방향 만들기
        int[][] newEdge = new int[edges.length*2][edges.length];
        for(int i = 0; i < edges.length; i++) {
            newEdge[2*i] = edges[i];
            newEdge[2*i+1][0] = edges[i][1];
            newEdge[2*i+1][1] = edges[i][0];
            newEdge[2*i+1][2] = edges[i][2];
        }


        int[] dist = new int[v];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        for (int i = 0; i < v - 1; i++) {
            for (int[] edge : newEdge) {
                int u = edge[0]; // 시작 정점
                int vEnd = edge[1]; // 끝 정점
                int weight = edge[2]; // 가중치
                if (dist[u] != INF && dist[vEnd] > dist[u] + weight) {
                    dist[vEnd] = dist[u] + weight;
                }
            }
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int vEnd = edge[1];
            int weight = edge[2];
            if (dist[u] != INF && dist[vEnd] > dist[u] + weight) {
                System.out.println("음수 사이클이 있어요");
                return false;
            }
        }

        for (int i = 0; i < v; i++) {
            System.out.print((dist[i] == INF ? "INF" : dist[i]) + " ");
        }
        System.out.println();

        return true;
    }
}

 

메인

 

package Path;


public class Main {

    public static void main(String[] args) {
        int vertex = 8; // 정점의 개수
        int start = 0;  // 시작 노드의 번호
        int[][] edge = {
                {0, 1, 9}, {0, 3, 1}, {0, 4, 6},
                {1, 2, 6}, {1, 3, 4},
                {2, 1, 1}, {2, 5, 7},
                {3,1,2},
                {4,7,1},
                {5,1,8}, {5,3,5},{5,6,8},
                {6,5,3}
        };

        Bellman bellman = new Bellman();
        bellman.findPath(vertex, edge, start);

    }
}

 

실행화면

 

결과 배열의 각 index 요소가 시작 노드부터 해당 index 번호의 노드까지 최단거리이다.