[AIGORITHM THEORY] FLOYD WARSHALL (플로이드 워셜) 개념정리

개념

특징

• 모든 정점의 쌍 u와 v간의 최단경로를 구하는 알고리즘
• Ak[i][j]
  • 0부터 k까지의 정점만을 이용한 정점 i에서 정점 j까지의 최단 경로
  • 정점 0부터 정점 k-1까지의 정점을 고려한 최단 거리 Ak-1을 구한 상태에서 다음 정점k를 고려할 때, 중간에 정점 k를 통과하지 않는 경로와 정점 k를 통과하는 경로 중 경로의 길이가 작은 것을 최단 경로로 택함
  • A-1[i][j] = cost[i][j] : 초기 상태, 가중치 인접 행렬의 가중치 값
  • A-1→A0→A1→... 순서로 경로에 정점을 늘려가면서 최단 경로를 구하다가 최종적으로An-1을 구하면 n개의 모든 정점 사이의 최단 경로를 구하게 됨

원리

• 모든 노드간의 최단거리를 구해야하기에, 2차원 인접 행렬을 구성한다. 알고리즘은 여러 라운드로 구성된다.
• 라운드마다 각경로에서 새롭게 중간노드로 활용할수 있는 노드를 선택하고, 더 짧은 길이를 선택해 줄이는 과정을 반복한다.

소스코드를 통한 구현

• 플로이드-위셜 알고리즘은 시간 복잡도가 O(n^3) 이기 때문에, 알고리즘을 적용하더라도 문제가 풀릴 때에만 사용할 수 있다.
• 최단 거리 배열인 dist 배열을 초기화 한다.
• for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if (i==j) dist[i][j]= 0; elseif (adj[i][j]) dist[i][j]= adj[i][j]; else dist[i][j]= INF; } }
• 이후, 각 라운드별로 중간 노드가 될 노드 번호를 for문 가장 바깥의 k로 정한다. 내부 이중 for문에는 i, j를 통해 각 노드별 모든 거리를 살펴보면서 k를 중간 노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 업데이트한다. (3중for문)
• for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ dist[i][j]= min(dist[i][j], dist[i][k]+dist[k][j]); } } }

시간복잡도

• O(n^3)

---

필기

• 다익스트라가 하나의 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘 이였다면, 플로이드-워셜 알고리즘은 한번 실행해서 모든 노드간 최단 경로를 구할 수 있다.
• 플로이드-워셜 알고리즘은 다익스트라와 다르게 음의 간선도 사용할 수 있다.
• 각 라운드별로 진행되는 과정을 사진으로 첨부!

예제 문제!

• 2606번 - 바이러스 : https://www.acmicpc.net/problem/2606
• 11404번 - 플로이드 : https://www.acmicpc.net/problem/11404

---

코드

• 기본적인 알고리즘 구현

INF = int(1e9)  # 무한대 값을 표현하기 위해 10억으로 설정
# 노드 개수, 간선 개수 입력받기
n, m = map(int, input().split())
graph = [[INF]*(n+1) for _ in range(n+1)]

# 자기 자신에게 가는 비용은 0으로 초기화
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

# 모든 간선 정보 입력받기
for _ in range(m):
    # u에서 v로 가는 비용 c
    u, v, c = map(int, input().split())
    graph[u][v] = c

# Floyd-Warshall 알고리즘 수행
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

# 모든 정점에서의 최단 거리 비용 출력
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            print('INFINITY', end=' ')
        else:
            print(graph[i][j], end=' ')
            print()

---

참고자료

• 감사하신 홍정희 교수님의 강의자료
• https://velog.io/@kimdukbae/플로이드-워셜-알고리즘-Floyd-Warshall-Algorithm
• https://chanhuiseok.github.io/posts/algo-50/