벨만포드 알고리즘(JAVA)

정리!

- 한정점에서 모든 정점으로의 최단거리(반면, 플로이드 워셜은 모든정점 쌍간)

- 엣지중심 (엣지리스트 사용)

- 음수 가중치 가능

- 음수 사이클 탐지

- O(VE)

-  초기화, 간선완화(모든 간선에 대해 최대 V-1반복 & 최단거리 갱신), 음수사이클 유무확인(V-1넘으면)

 

정의

벨만-포드 알고리즘은 그래프에서 특정 출발 노드로부터 다른 모든 노드까지의 최단거리를 구하는 알고리즘입니다.
이 알고리즘은 다익스트라 알고리즘과 달리 음수 가중치의 엣지가 있는 그래프에서도 동작하며,
음수 사이클(노드를 여러 번 거쳐서 가중치의 합이 음수가 되는 경로)이 있는지도 탐지할 수 있습니다.
▶ 실제 코딩 테스트에선 음수사이클읜 존재여부를 판단 할 때 많이 사용되는 알고리즘이기도 합니다.

특징

• 출발 노드와 모든 노드 간 최단거리를 탐색합니다: 벨만-포드 알고리즘은 출발 노드로부터 다른 모든 노드까지의 최단거리를 계산합니다. 다익스트라 알고리즘과는 달리, 음수 가중치가 있는 그래프에서도 사용 가능합니다.
• 음수 사이클을 탐지할 수 있습니다: 벨만-포드 알고리즘은 그래프에 음수 사이클이 있는지 확인할 수 있습니다. 만약 음수 사이클이 존재한다면, 최단거리를 구할 수 없다고 판단할 수 있습니다.
  
  

알고리즘 동작 과정

벨만-포드 알고리즘의 기본적인 동작 과정은 다음과 같습니다:

1. 초기화: 출발 노드에서 자신으로의 거리는 0, 다른 모든 노드로의 거리는 무한대(INF)로 설정합니다.
2. 간선 완화(Edge Relaxation): 모든 간선에 대해 최대 'V-1'번을 반복하여, 최단 거리를 갱신합니다. 
                                                                                       *(V-1이 최단거리를 구성할 수 있는 엣지 갯수 이므로)
3. 음수 사이클 확인: V-1번 반복 후에도 거리가 더 줄어드는 경우, 음수 사이클이 존재한다고 판단합니다.
   ▶ 최단거리에 필요한 최대 엣지 갯수인 V-1개의 엣지로 최단거리 업데이트를 완료하고
      한번 더 업데이트를 시도했는데 업데이트(최단거리가 갱신)가 된다면, 이는 음수사이클이 존재한다는 의미와 같게됩니다.

시간 복잡도

벨만-포드 알고리즘의 시간 복잡도는 다음과 같습니다:

• O(VE) (V: 노드의 수, E: 엣지의 수)

이는 모든 간선에 대해 V-1번 반복하기 때문입니다.

 

---

예제

아래와 같은 그래프가 있다고 가정해보겠습니다.

오리가 도착점, 라이언이 출발점

* 다시 보니 화살표를 반대로 그려 수정했습니다...

 

 

이해를 돕기 위해 입력을 섞어서 아래 순서로 받겠습니다.

edges[0] = new Edge(0, 1, 7);  // 1 -> 2, 가중치 7
edges[1] = new Edge(4, 3, -1);  // 5 -> 4, 가중치 -1
edges[2] = new Edge(1, 4, 5);   // 2 -> 5, 가중치 5
edges[3] = new Edge(2, 3, 7);   // 3 -> 4, 가중치 7
edges[4] = new Edge(0, 2, 3);   // 1 -> 3, 가중치 3
edges[5] = new Edge(3, 1, -3);  // 4 -> 2, 가중치 -3

 

 

1. 초기화:

출발 노드를 1로 설정합니다.
각 노드까지의 최단거리를 저장하는 dist 배열을 초기화합니다. 초기에는 출발 노드 1까지의 거리는 0으로 설정하고, 나머지 노드들은 무한대(INF)로 설정합니다.

 

dist[V]

1	2	3	4	5
0	MAX	MAX	MAX	MAX

 

 

2. 간선 완화(Edge Relaxation):

모든 간선에 대해 V-1번(노드의 수 - 1) 반복하면서 거리 갱신을 시도합니다.

 

- 1번째 반복 (i = 0):

• 간선 1 -> 2: dist[1] + 7 < dist[2] → dist[2] = 7
• 간선 5 -> 4: 출발지 5의 dist는 무한대, 갱신 없음.
• 간선 2 -> 5: dist[2] + 5 < dist[5] → dist[5] = 12
• 간선 3 -> 4: dist[3] + 7 < dist[4] → dist[4] = 3 + 7 = 10
• 간선 1 -> 3: dist[1] + 3 < dist[3] → dist[3] = 3
• 간선 4 -> 2: 출발지 4의 dist는 무한대, 갱신 없음.

1번째 반복 후 상태:

1	2	3	4	5
0	7	3	INF	12

 

 

- 2번째 반복 (i = 1):

• 간선 1 -> 2: dist[1] + 7 < dist[2] → dist[2] = 7 (변경 없음)
• 간선 5 -> 4: dist[5] - 1 < dist[4] → dist[4] = 11
• 간선 2 -> 5: dist[2] + 5 < dist[5] → dist[5] = 12 (변경 없음)
• 간선 3 -> 4: dist[3] + 7 < dist[4] → dist[4] = 10 (변경 없음)
• 간선 1 -> 3: dist[1] + 3 < dist[3] → dist[3] = 3 (변경 없음)
• 간선 4 -> 2: dist[4] - 3 < dist[2] → dist[2] = 7

2번째 반복 후 상태:

1	2	3	4	5
0	7	3	10	12

 

 

- 3번째 반복 (i = 2):

1	2	3	4	5
0	7	3	10	12

 

- 4번째 반복 (i = 3):

1	2	3	4	5
0	7	3	10	12

- 5번째 반복 (i = 4):

1	2	3	4	5
0	7	3	10	12

 

 

3. 음수 사이클 확인:

모든 간선에 대해 한 번 더 검사하여, 거리가 더 줄어드는 경우가 있는지 확인합니다.

이 경우, 거리 갱신이 발생하지 않으므로 음수 사이클이 없음을 확인할 수 있습니다.

음수 사이클이 없다면 V-1번 반복한 배열이 출발노드(1)에서 도착노드(Index)까지의 최단거리임

---

전체 코드 (JAVA)

import java.util.Arrays;

class BellmanFord {
    // 간선을 정의하는 클래스
    static class Edge {
        int source, destination, weight;
        Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    // 벨만-포드 알고리즘 구현
    public static void bellmanFord(Edge[] edges, int V, int E, int source) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);  // 초기 거리를 무한대로 설정
        dist[source] = 0;

        // V-1번 반복
        for (int i = 0; i < V - 1; i++) {
            for (int j = 0; j < E; j++) {
                int u = edges[j].source;
                int v = edges[j].destination;
                int weight = edges[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        // 음수 사이클 체크
        for (int j = 0; j < E; j++) {
            int u = edges[j].source;
            int v = edges[j].destination;
            int weight = edges[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("그래프에 음수 사이클이 존재합니다.");
                return;
            }
        }

        printSolution(dist, V);
    }

    // 최종 결과 출력 함수
    public static void printSolution(int[] dist, int V) {
        System.out.println("노드 1로부터 각 노드의 최단거리:");
        for (int i = 0; i < V; i++) {
            System.out.println("노드 1 -> 노드 " + (i + 1) + ": " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int V = 5; // 노드의 수
        int E = 6; // 간선의 수

        Edge[] edges = new Edge[E];

        // 간선들 정의
        edges[0] = new Edge(0, 1, 7);  // 1 -> 2, 가중치 7
        edges[1] = new Edge(4, 3, -1);  // 5 -> 4, 가중치 -1
        edges[2] = new Edge(1, 4, 5);   // 2 -> 5, 가중치 5
        edges[3] = new Edge(2, 3, 7);   // 3 -> 4, 가중치 7
        edges[4] = new Edge(0, 2, 3);   // 1 -> 3, 가중치 3
        edges[5] = new Edge(3, 1, -3);  // 4 -> 2, 가중치 -3

        bellmanFord(edges, V, E, 0);
    }
}

 

---

정리

벨만포드 알고리즘은 음수 가중치가 포함된 그래프에서 최단 경로를 찾을 수 있으며, 음수 사이클을 탐지할 수 있습니다.

각 반복에서 모든 간선을 검사하여, 거리 배열을 최대 V-1번 갱신합니다.

이 알고리즘은 모든 노드와 간선에 대해 최단 거리를 점진적으로 계산하며, 음수 사이클이 존재할 경우 이를 탐지할 수 있습니다.