플로이드-워셜

• 플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
• 모든 노드 간에 최단 거리를 탐색
• 음수 가중치 엣지가 있어도 수행 가능 단, 음수 사이클이 있으면 안된다.
• 동적 계획법의 원리를 이용해 알고리즘에 접근한다.

• 대부분 플로이드-워셜 알고리즘을 사용하는 노드의 개수는 200,100개 정도이다.

플로이드-워셜의 핵심 이론

• 플로이드-워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.

• 위 그림에서 색칠된 엣지 경로가 1→5 최단 경로라면 1→4 최단 경로와 4→5 최단 경로 역시 색칠된 엣지로 이뤄질 수 밖에 없다.
• 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다는 의미가 된다.
• 이 원리로 다음과 같은 점화식을 도출할 수 있다.

🌸 도출한 플로이드-워셜 점화식

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 문의 형태로 반복하면서 리스트의 값을 업데이트한다.

🌸 플로이드-워셜 알고리즘 로직

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])

플로이드-워셜은 위의 3중 for문만 외우면 된다.

---

출처- 하루코딩