플로이드 와샬(Floyd-Warshall)
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘이다.
👉 최단경로를 구하는 다익스트라와 다른점은?
다익스트라는 ‘한 지점에서 다른 특정 지점까지의 최단 경로’를 구하는 알고리즘인 반면, 플로이드 와샬은 모든 노드에 대한 최단 경로를 찾는 것이 목적이다.
또한 다익스트라는 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾아야 하는데, 플로이드 와샬은 찾지 않아도 된다.
마지막으로, 다익스트라는 최단거리를 1차원 리스트에 저장하는데, 플로이드 와샬은 2차원 리스트에 저장한다는 특징이 있다.
[요약]
- 다익스트라 → 그리디, 특정 노드, 1차원 리스트 최단거리
- 플로이드 와샬 → 다이나믹 프로그래밍, 모든 노드, 2차원 리스트 최단거리
동작 과정
- 노드의 개수가 N일 때, N번 만큼의 단계를 반복하여 점화식에 맞게 2차원 리스트를 갱신한다.
- 각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다.
A → 1번 노드 → B 로 가는 최단 거리 비용은?
- A → B로 가는 비용과 1번을 거쳐서 가는 비용과 작은 것이 최단 거리 비용이 된다.
따라서 현재 확인하고 있는 노드를 제외하고 N-1개의 노드 중에서 다른 노드 (A, B) 쌍을 선택한다.
경우의 수와 시간 복잡도는 다음과 같다.
점화식
시간복잡도
총 시간 복잡도는 N번의 단계만큼 반복하므로, 이다.
코드
n = int(input())
k = int(input())
# 이차원 행렬 그래프 만들기
INF = int(1e9) # 초기값 무한으로.
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
# 연결 정보 업데이트
for _ in range(k):
a, b, c = map(int, input().split())
graph[a][b] = c # a에서 b노드까지 c 만큼 소요
# 자기자신 -> 자기자신 비용은 0으로 설정
for i in range(1, n+1):
for j in range(1, n+1):
if i == j:
graph[i][j] = 0
# 점화식에 따라 플로이드 와샬 알고리즘 수행
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):
# 도달할 수 없는 경우 무한(INFINITY)이라고 출력
if graph[i][j] == INF:
print("INFINITY", end = ' ')
else:
print(graph[i][j], end = ' ')
print()
# 입력값
# 4
# 7
# 1 2 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2
참조
이것이 코딩 테스트다 - 나동빈
Uploaded by N2T
