개념
특징
- 모든 정점의 쌍 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()참고자료
해보자! 게임 클라 개발자!