Colin's Blog
[c++] 플로이드-와샬 알고리즘

플로이드-와샬 알고리즘은 그래프에서 모든 정점 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 동적 프로그래밍을 활용하여 효율적으로 모든 정점 쌍 간의 최단 경로를 계산합니다. 플로이드-와샬 알고리즘은 음의 가중치가 있는 그래프에서도 사용할 수 있습니다.

알고리즘 원리

플로이드-와샬 알고리즘의 간단한 설명을 살펴보겠습니다. 정점의 개수를 n이라고 하겠습니다. 또한, graph[][] 배열을 그래프의 인접 행렬로 초기화합니다. 각 정점에서 다른 정점으로의 직접적인 경로가 있을 경우, 해당 값으로 초기화하고, 직접적인 경로가 없을 경우 무한대를 나타내는 값으로 초기화합니다.

그 후, i번째 정점을 거쳐가는 경로를 고려하여 더 짧은 경로로 갱신합니다. 즉, graph[i][j] 값과 graph[i][k] + graph[k][j] 값을 비교하여 갱신합니다. 이를 i번째 정점에 대해 0부터 n-1까지 모든 정점에 대해 반복하며 수행합니다.

아래는 플로이드-와샬 알고리즘의 적용 예시입니다. 두 정점 간의 최단 경로를 찾는 과정을 표로 나타냈습니다.

  0 1 2 3
0 0 3 8 ∞
1 ∞ 0 2 ∞
2 ∞ ∞ 0 1
3 1 ∞ ∞ 0

위의 표에서 각 셀은 해당 정점 쌍 사이의 최단 경로를 나타냅니다. 표에 따르면, 0번 정점에서 2번 정점으로 가는 최단 경로의 길이는 3입니다.

시간 복잡도

플로이드-와샬 알고리즘의 시간 복잡도는 O(n^3)입니다. 이 알고리즘은 각 정점을 거쳐가는 경우를 고려하고, 모든 정점 쌍 간의 최단 경로를 찾기 때문에 이러한 시간 복잡도를 갖게 됩니다.

예제 코드

다음은 C++로 구현된 플로이드-와샬 알고리즘의 간단한 예제 코드입니다.

#include <iostream>
#define INF 99999

void floydWarshall(int graph[][4]) {
  int dist[4][4];

  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      dist[i][j] = graph[i][j];
    }
  }

  for (int k = 0; k < 4; k++) {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
}

플로이드-와샬 알고리즘을 이용하면, 그래프의 모든 정점 쌍 간의 최단 경로를 효과적으로 찾을 수 있습니다.

결론

플로이드-와샬 알고리즘은 그래프의 모든 정점 쌍 간의 최단 경로를 찾는 효과적인 방법을 제공합니다. 이 알고리즘은 동적 프로그래밍을 기반으로 하고 있어, 그래프의 가중치에 제약이 없는 경우에 유용하게 사용됩니다.

추가 자료

© 2018 Colin. All rights reserved.