벨만 포드 알고리즘

벨만-포드 알고리즘은 모든 정점 간의 최단 경로를 찾기 위한 알고리즘 중 하나이다.

다익스트라 알고리즘이 간선의 가중치가 음수일 때 제대로 동작하지 않는 경우가 있지만, 벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서도 사용할 수 있다.

알고리즘의 기본 아이디어는 각 정점에 대해 현재까지 발견한 최단 경로의 추정치를 저장하고, 이를 반복적으로 업데이트하여 최종적으로 최단 경로를 찾아내는 것이다.

그리고 마지막에 음의 사이클이 있는지를 확인하여 음의 사이클이 있다면 최단 경로를 정의할 수 없다는 것을 알 수 있다.

시간 복잡도는 O(VE)이다.

알고리즘 동작 원리

---

1. 초기화: 시작 정점을 제외한 모든 정점에 대한 최단 거리를 무한대로 초기화하고, 시작 정점의 최단 거리를 0으로 설정한다.
2. 모든 에지를 확인해 정답 배열 업데이트: 최단거리를 알 수 있는 점정(초기에는 시작 정점)에서 출발하는 에지들을 사용하여 갈 수 있는 정점들에 최단거리를 구한다.
3. 업데이트 반복:  V-1번 반복한다. 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 V-1개를 넘을 수 없기 때문이다.
4. 음의 사이클 확인: V-1번 반복 이후에 만약 정점 간의 최단 거리가 갱신되는 경우, 음의 사이클이 존재할 수 있다. 따라서 한 번 더 간선을 모두 확인하여 음의 사이클이 있는지 검사한다.

 

import java.util.Arrays;

class BellmanFord {
    static class Edge {
        int src, dest, weight;

        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    static void bellmanFord(int V, Edge[] edges, int src) {
        // 최단거리 배열
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[src] = 0;

        // 노드 개수-1번 업데이트 반복
        for (int i = 1; i < V; ++i) {
            for (Edge edge : edges) {
                int u = edge.src;
                int v = edge.dest;
                int weight = edge.weight;
                
                // 시작 정점까지의 거리를 알 수 없다면 에지를 사용할 수 없다.
                if (distance[u] == Integer.MAX_VALUE) continue;
                
                // 이전에 구했던 거리, 현재 에지를 사용했을 때 거리중 최소 거리를 최단 거리로 업데이트.
                distance[v] = Math.min(distance[u] + weight, distance[v]);
            }
        }

        // 음의 사이클 확인
        for (Edge edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;
            
            if (distance[u] == Integer.MAX_VALUE) continue;
            
            if (distance[u] + weight < distance[v]) {
                System.out.println("그래프에 음의 사이클이 존재합니다.");
                return;
            }
        }

        // 최단 거리 출력
        System.out.println("정점 간 최단 거리:");
        for (int i = 0; i < V; ++i)
            System.out.println("정점: " + i + " 최단 거리: " + distance[i]);
    }
}