bellman ford

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

시간복잡도 : O(VE) (거의 N^2)

벨만 포드 알고리즘은 그래프 상에 존재하는 두 노드 간의 최단 거리를 구할 때 사용한다.

이는 다이크스트라 알고리즘 O((V + E) log_2(V)) 에 비해서 느리다.

그러나 이 알고리즘은 간선 cost가 음수일 때도 사용할 수 있다.

벨만 포드 알고리즘의 전제 조건은 다음과 같다.

• 최단 경로는 사이클을 포함할 수 없기 때문에, 최대 (V - 1)개의 간선만 사용할 수 있다.
• 최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해주고, 음의 가중치로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.

음수 사이클 안에서 무한히 탐색하는 것을 피하는 방법은 탐색 횟수를 V−1번으로 제한하는 것이다. (시작 정점에서 특정 정점까지 도달하기 위해 거치는 최대 간선 수는 V−1개 이기 때문)

프로세스

1. 시작 정점을 결정한다.
2. 시작 정점부터 다른 정점까지 거리 값 모두 무한대로 초기화한다. (시작 정점은 0으로 초기화)
3. 현재 정점의 모든 인접 정점들을 탐색하며, 기존에 기록된 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧다면 인접 정점까지의 거리를 갱신한다.
4. 3번 과정을 V − 1번 반복한다.
5. 위 과정을 모두 마친 후에도 거리가 갱신되는 경우가 있다면 그래프에 음수 사이클이 존재한다는 것을 알 수 있다.

#define INF 9876543210

struct Edge {
  int to; // 목적지 정점 번호
  int cost; // 목적지 까지의 비용
};

vector<vector<Edge>> graph;
vector<int> costs;

bool bellman_ford(int start_index) {
  for (int i = 1; i <= N; i++) {
    costs[i] = INF;
  }
  costs[start_index] = 0;

  bool isCycle = false;
  for (int from = 1; from <= N; from++) {
    for (int to = 1; to <= N; to++) {
      for (Edge current : graph[to]) {
        int new_val = costs[to] + current.cost;
        int before_val = costs[current.to];

        if (before_val > new_val) {
          costs[current.to] = new_val;

          if (from == N) {
            isCycle = true;
          }
        }
      }
    }
  }

  return isCycle;
}