Bellman Ford

벨만 포드(Bellman Ford) 알고리즘에 대해 알아보려고 한다. (자세한 부분은 아래 페이지 참조)

https://www.geeksforgeeks.org/bellman-ford-algorithm-simple-implementation/

https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/

벨만 포드 알고리즘을 알아보기 전에 흔히 알려진 다익스트라 알고리즘은 시작점으로부터 그래프 상의 모든 정점까지의 최단 거리를 찾아준다. 그러나 간선 값이 양수가 아닌 음수일 경우에는 정상적으로 알고리즘을 사용할 수 없다. 바로 이 시점에 등장한 것이 벨만 포드 알고리즘이다.

즉, 간선 값이 음수 일 경우에도 시작점으로부터 모든 정점까지의 최단 거리를 찾아 준다. 물론 단점은 다익스트라보다 시간 복잡도가 크다는 것이다. (VLogV vs VE)

간단히 동작 방식을 알아보면,

1) 시작점을 제외한 모든 정점을 "큰 값"으로 초기화 한다.

2) 가장 짧은 거리를 찾는다.

즉, u-v 간선에 대해서 "dist[v] > dist[u] + u-v 값" 일 때, "dist[v]를 dist[u] + u-v 값"으로 갱신한다.

좀 더 이해하기 쉽게 그림을 바탕으로 다시 설명해보면,

시작점이 A라고 할 때, A를 제외한 모든 정점의 값을 "무한대"로 초기화한다. 

(모든 간선은 정점의 총 개수 - 1 번 계산된다. 즉, 여기서는 4번)

그리고 모든 간선에 대해 다음 순서로 진행된다. (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D) 

참고로, 위에서 언급한 순서는 다르게 적용될 수 있다. (여기서는 예시를 위한 것일 뿐이다.)

첫 번째 열이 초기화된 값이라면 두 번째 열부터는 실제 변경되는 값이 저장된다.

위의 그림을 보면 알 수 있듯이 A->B, A->C 값이 변화되는 것을 볼 수 있다. 특히, A->C는 A->C로 직접적인 접근보다 A->B->C로 우회에서 접근하는 것이 더 빠르다는 것을 알 수 있다.

모든 간선에 대해 값이 위의 그림처럼 된다. (각 간선에 대해 계산 할 때마다 변경될 수 있다.)

이렇듯 벨만 포드 알고리즘은 정점과 간선의 값을 계속 업데이트하면서 최단 거리를 찾는다. 앞서 모든 정점 - 1 번 계산된다고 언급했듯이 최종적인 최단 거리를 찾기 위해서는 각 간선에 대해 모든 정점 - 1번 계산이 되어야 한다. (물론 값이 바뀌지 않을 수 있다.)

대략적으로 알아 보았으니 코드를 살펴보도록 하자.

// 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(struct Graph* graph, int src) {     int V = graph->V;     int E = graph->E;     int dist[V];        // Step 1: Initialize distances from src to all other vertices     // as INFINITE     for (int i = 0; i < V; i++)         dist[i] = INT_MAX;     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 - 1; 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] != INT_MAX && 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 i = 0; i < E; i++) {         int u = graph->edge[i].src;         int v = graph->edge[i].dest;         int weight = graph->edge[i].weight;         if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {             printf("Graph contains negative weight cycle");             return; // If negative cycle is detected, simply return         }     }        printArr(dist, V);        return; }

코드는 생각보다 간단하다. 모든 간선을 정점 - 1번 반복하면서 최단 거리를 찾는다.

즉, dist[u] + weight < dist[v] 이면, dist[v] = dist[i] + weight이다.

그런데 비슷하 계산이 한 번 더 이루어지는데, 이는 간선사이의 음수를 찾기 위함이다. 

일반적으로 음수 없이 최단거리가 찾아져야 하겠지만, 음수가 있을 경우 해당 그래프는 cycle이 발생한다는 것이다. (음수가 있으면 계산 할 때마다 값이 줄어들기 때문)