벨만포드 최단거리 알고리즘

벨만포드 알고리즘

이 글은 GeeksforGeeks의 Bellman–Ford Algorithm | DP-23를 번역한 글입니다.

그래프와 그래프의 source 정점 src를 고려하여, src부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라와 차이점은 그래프의 간선이 음의 값을 가질 수 있다는 점이다. 최단 거리문제는 다익스트라를 활용하여 해결할 수 있다. 다익스트라 알고리즘은 그리디 알고리즘 이며 피보나치 힙을 사용한다면 O(VlogV)의 시간 복잡도를 가졌다. 하지만 다익스트라는 음의 값을 가진 그래프에서는 사용할 수 없으며, 벨만포드를 사용하여야 한다. 벨만포드는 다익스트라보다 간단하며 분산 시스템에 잘 맞다. 하지만 시간 복잡도는 O(VE)로 다익스트라보다 복잡하다.

알고리즘

Input : 그래프와 source 정점 src

Output : src로 부터 모든 정점의 최단거리. 만약 음의 사이클이 존재한다면 최단거리는 계산되지 않고, 음의 사이클을 찾아낸다.

1) 첫번째로 src로 부터 모든 정점의 거리를 무한대로 초기화 한다. 그리고 src의 거리는 0으로 초기화 한다.  정점의 개수만큼의 dist[] 배열을 만든다.
​
2) 다음으로 최단거리를 계산한다. |V|-1 번 만큼 아래 단계를 반복한다.
​
    a)  dist[v] > dist[u] + 간선 uv의 가중치 라면 dist[v]를 dist[u]+ 간선 uv의 가중치로 갱신한다.
​
3) 만약 음의 사이클이 존재한다면 다음 과 같은 상황이 발생한다.

만약 ( dist[v] > dist[u] + 간선 uv의 가중치 )라면, 음의 가중치가 존재하는 것이다. step3의 아이디어는 step2가 음의 가중치를 포함하지 않으면 가장 짧다는 것을 보장한다. 만약 모든 간선에 대하여 한번더 반복하여 더 짧은 최단거리를 얻는다면, 음의 사이클이 존재한다는 것이다.

어떻게 동작하는가? 다른 다이나믹 프로그래밍 문제들 처럼, 이 알고리즘은 문제를 바텀업(Bottom-up)의 방법으로 해결한다. 첫번째 탐색에서 간선이 최대 하나 포함된 최단거리가 구해진다. 다음으로 최대 2개의 간선이 포함된 최단거리가 구해지는데 그래서 i q번째 반복 이후에 최대 i개의 간선이 포함된 최단 거리가 구해진다. 이 그래프에는 최대 |V|-1개의 단순 경로가 있을 수 있기 때문에 |V|-1번 반복된다. 이 아이디어는 음의 경로가 없음을 가정한다. 만약 i번 이상의 최단경로가 구해진다면 모든 경로는 최대 (i+1)개의 간선이 포함된 최단경로임을 보장하게 된다.

예제

다음의 예제와 함께 알고리즘을 이해해보자.

모든 정점까지의 거리를 무한대로 초기화하고 시작 정점 src의 거리를 0으로 초기화 한다. 이 그래프에서 간선의 개수는 5개이며 모든 과정은 4번만 이루어 저야한다.

다음 순서로 진행한다. (B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D). 위의 첫번째 과정을 거치고 나면 다음과 같은 거리값이 구해진다. 두번째 줄은 (B,E), (D,B), (B,D)와 (A,B)의 과정이 진행한 거리 값을 보여준다.

첫번째 반복은 최단거리가 1개이상의 간선을 포함함을 보장한다. 두번째 반복이 이루어지만 다음과 같은 거리가 구해진다. (마지막 줄이 2번째 반복의 최종결과 값이다.)

두번째 반복은 모든 최단거리가 최대 2개의 간선을 포함함을 보장한다. 모든 과정은 간선을 2번이상 처리한다. 거리는 두번째 반복 후에 최소화되므로 세번째 및 네번째 반복은 거리를 업데이트하지 않는다.

자바소스

class Graph 
{ 
    // A class to represent a weighted edge in graph 
    class Edge { 
        int src, dest, weight; 
        Edge() { 
            src = dest = weight = 0; 
        } 
    }; 
  
    int V, E; 
    Edge edge[]; 
  
    // Creates a graph with V vertices and E edges 
    Graph(int v, int e) 
    { 
        V = v; 
        E = e; 
        edge = new Edge[e]; 
        for (int i=0; i<e; ++i) 
            edge[i] = new Edge(); 
    } 
  
    // The main function that finds shortest distances from src 
    // to all other vertices using Bellman-Ford algorithm.  The 
    // function also detects negative weight cycle 
    void BellmanFord(Graph graph,int src) 
    { 
        int V = graph.V, E = graph.E; 
        int dist[] = new int[V]; 
  
        // Step 1: Initialize distances from src to all other 
        // vertices as INFINITE 
        for (int i=0; i<V; ++i) 
            dist[i] = Integer.MAX_VALUE; 
        dist[src] = 0; 
  
        // Step 2: Relax all edges |V| - 1 times. A simple 
        // shortest path from src to any other vertex can 
        // have at-most |V| - 1 edges 
        for (int i=1; i<V; ++i) 
        { 
            for (int j=0; j<E; ++j) 
            { 
                int u = graph.edge[j].src; 
                int v = graph.edge[j].dest; 
                int weight = graph.edge[j].weight; 
                if (dist[u]!=Integer.MAX_VALUE && 
                    dist[u]+weight<dist[v]) 
                    dist[v]=dist[u]+weight; 
            } 
        } 
  
        // Step 3: check for negative-weight cycles.  The above 
        // step guarantees shortest distances if graph doesn't 
        // contain negative weight cycle. If we get a shorter 
        //  path, then there is a cycle. 
        for (int j=0; j<E; ++j) 
        { 
            int u = graph.edge[j].src; 
            int v = graph.edge[j].dest; 
            int weight = graph.edge[j].weight; 
            if (dist[u] != Integer.MAX_VALUE && 
                dist[u]+weight < dist[v]) 
              System.out.println("Graph contains negative weight cycle"); 
        } 
    }
}