[알고리즘] 플로이드-워셜

플루이드

- 음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점에 까지의 최단거리를 모두 구할 수 있는 알고리즘

- 음의 가중치를 갖는 간선이 존재해도 상관없음

   - 다익스트라는 음의 가중치를 가질 수 없음

- 다이나믹 프로그래밍 기법을 사용한 알고리즘

- 인접행렬을 이용하여 각 노드가 최소 비용 계산

- 시간 복잡도가 복잡해 입력의 크기가 크면 곤란하다~ (시간복잡도 O(V^3))

- 플로이드 워셜을 사용하는 문제는 일반적으로 노드의 개수의 범위가 다른 그래프에 적게 나타남

 

점화식

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

순서

1. 배열을 선언하고 초기화하기

• D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열
• S와 E의 값이 같은 같은 0, 다른 칸은 무한으로 초기화
• S == E는 자기 자신에게 가는데 걸리는 최단 경로값을 의미

2. 최단 거리 배열에 그래프 데이터 저장하기

• 출발 노드는 S, 도착 노드는 E, 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 배열에 저장
• 이로써 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현하다는 것을 알 수 있음

3. 점화식으로 배열 업데이트하기

for 경유지 K에 관해 (1~N)
	for 출발 노드 S에 관해 (1~N)
		for 도착 노드 E에 관해 (1~N)
		D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])