2023. 05. 22.
플로이드-워셜 (floyd-warshall) 📌
플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 시작점이 있는 것이 아니라 모든 노드 간의 최단 경로를 탐색한다. 음수 가중치 에지가 있어도 되며(but cycle이 존재하면 안됨) 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간복잡도는 O(V^3)으로 다른 알고리즘에 비해 느린 편에 속하므로 플로이드-워셜 알고리즘을 사용해야 하는 문제가 나오면 일반적으로 노드 개수의 범위가 다른 그래프에 비해 적게 나타나는 것을 알 수 있다.
시간복잡도: O(V^3) 노드 수: V
- 아래 사진을 보면 색칠된 에지 경로가 노드 1부터 노드 5까지 가는 최단 경로라면 노드 1 -> 노드 4의 최단 경로와 노드 4 -> 노드 5의 최단 경로 역시 색칠된 에지로 이뤄질 수 밖에 없다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다는 의미이므로 동적 계획법과 같이 아래의 점화식을 도출할 수 있다.
D[S][E] = min(D[S][E], D[S][K] + D[K][E])
플로이드-워셜의 핵심 이론
📢 플로이드-워셜 구현 과정
1. 리스트를 선언하고 초기화하기
- D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의한다. 여기에서 S와 E의 값이 같은 경우는 자기 자신한테 가는 최단 경로값을 의미하므로 0으로 초기화하고 나머지는 무한대로 초기화한다.
2. 최단 거리 리스트에 그래프 데이터 저장하기
- 출발 노드는 S, 도착 노드는 E, 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 리스트에 입력한다. 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한다.
3. 점화식으로 리스트 업데이트하기
- 기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 리스트의 값을 업데이트 한다.
for k in range(1, n+1): # 경유지 k, 경유지값이 항상 가장 바깥쪽 for문에 나와야 됨
for s in range(1, n+1): # 출발 노드 s
for e in range(1, n+1): # 도착 노드 e
distance[s][e] = min(distance[s][e], graph[s][k] + graph[k][e])
2023. 05. 22. 오늘의 문제풀이 ✍
BOJ 11404 - 플로이드
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
INF = sys.maxsize
graph = [[INF] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
graph[i][i] = 0
for _ in range(m):
s,e,cost = map(int,input().split())
if graph[s][e] > cost:
graph[s][e] = cost
for a in range(1, n+1):
for b in range(1, n+1):
for c in range(1, n+1):
graph[b][c] = min(graph[b][c], graph[b][a] + graph[a][c])
for j in range(1, n+1):
for k in range(1, n+1):
if graph[j][k] == INF:
print(0, end=' ')
else:
print(graph[j][k], end=' ')
print()출처
Do it algorithm
