[Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘이란?

플로이드-워셜 알고리즘은 그래프 내의 모든 정점 쌍에 대해 최단 경로를 찾는 알고리즘이다. 인접 행렬을 사용하여 구현되며, 그래프의 가중치가 음수일 수 있지만, 음수 사이클이 없는 경우에만 유효하다.

알고리즘의 기본 아이디어는 모든 가능한 경로를 시도하면서 더 짧은 경로가 발견되면 이를 갱신하는 것이다.

 

 

시간복잡도

플로이드-워셜 알고리즘의 시간 복잡도는 O(n^3)이다. 그래프의 모든 정점 쌍에 대해 경로를 확인하기 때문이다. 여기서 n은 그래프의 정점 수를 의미한다.

 

 

플로이드-워셜의 기본 원리

1. 초기화:
   • 각 정점 간의 최단 경로를 저장할 2차원 배열 dist를 초기화
   • 그래프의 직접 연결된 정점 사이의 가중치로 dist 배열을 설정
   • dist[i][i]는 0으로 초기화하고, 직접 연결이 없는 정점 쌍은 무한대로 설정.
2. 계산:
   • 모든 정점 k에 대해, dist[i][j]를 업데이트하여 정점 i에서 정점 j로 가는 경로가 k를 경유하는 것이 더 짧은 경우 탐색
   • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])를 반복적으로 적용
3. 응용:
   • 모든 쌍의 최단 경로를 계산하기 때문에, 그래프 내의 임의의 두 정점 사이의 최단 경로를 효율적으로 찾을 수 있다.
   • 그래프의 연결성 분석, 경로 최적화, 네트워크 설계 등 다양한 문제에 적용

 

 

 

예시

예시주어진 그래프에서 모든 정점 쌍 사이의 최단 경로를 계산하고, 이를 2차원 배열 dist에 저장하여 사용

예제 그래프:

    (2)
  A ----> B
  |      /|
 (4)  (1) |
  |  /    |
  v v     v
  D <---- C
    (3)

 

 

초기화 단계:

dist = [  [0, 2, ∞, 4],
  [∞, 0, 1, ∞],
  [∞, ∞, 0, 3],
  [∞, ∞, ∞, 0]
]

 

 

계산 단계:

1. k = 0 (A)일 때, dist 배열을 업데이트.
2. k = 1 (B)일 때, dist 배열을 업데이트.
3. k = 2 (C)일 때, dist 배열을 업데이트.
4. k = 3 (D)일 때, dist 배열을 업데이트.

 

최종 dist 배열:

dist = [  [0, 2, 3, 4],
  [∞, 0, 1, 4],
  [∞, ∞, 0, 3],
  [∞, ∞, ∞, 0]
]

이 최종 배열을 사용하여 그래프 내 모든 정점 쌍 사이의 최단 경로를 확인할 수 있습니다. 예를 들어, 정점 A에서 정점 C로 가는 최단 경로의 길이는 dist[0][2] = 3입니다.

출처: https://velog.io/@roo333/Floyd-Warshall-Algorithm