230214 벨만포드, Bellman-Ford

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

• 그래프 최단 경로 구하는 알고리즘
• 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함)
• 음수 사이클 없어야 함(음수 가중치 허용)
• O(nm) 시간 복잡도 가짐
• 동적 계획법 사용, relaxation 기법
  
  

최단 거리 구하는 알고리즘에서 출발지 하나를 고르는 것은 다익스트라와 같다. 다익스트라와 벨만-포드의 차이점은 아래와 같다.

class Edge {
    int src;
    int dest;
    int weight;

    Edge() {
        src = dest = weight = 0;
    }
}

class Graph {
    private static final int INF = Integer.MAX_VALUE;

    private int vertex;
    private Edge[] edges;

    Graph(int v, int e) {
        vertex = v;
        edges = new Edge[e];
        for (int i = 0; i < e; ++i)
            edges[i] = new Edge();
    }

    void bellmanFord(int src) {
        // Step 1: 원점에서 정점으로 가는 모든 거리를 INF로 초기화
        int[] dist = new int[vertex];
        Arrays.fill(dist, INF);
        dist[src] = 0;

        // Step 2: 모든 정점을 방문하여 거리 업데이트
        for (int i = 1; i < vertex; ++i) {
            for (Edge edge : edges) {
                int u = edge.src;
                int v = edge.dest;
                int weight = edge.weight;
                if (dist[u] != INF && dist[u] + weight < dist[v])
                    dist[v] = dist[u] + weight;
            }
        }
        
        // Step 3: 한번 더 반복하면서 음수 사이클을 찾아줌
        for (Edge edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                System.out.println("음수 사이클 존재");
                return;
            }
        }

        printDistances(dist);
    }

    void printDistances(int[] dist) {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < vertex; ++i)
            System.out.println(i + "\t\t" + dist[i]);
    }
}