[Algorithm] 플로이드-워셜(Floyd-warshall)

플로이드-워셜

• 플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 다음과 같은 특징을 가지고 있습니다.

기능	특징	시간 복잡도
모든 노드 간에 최단 경로 탐색	- 음수 가중치 간선이 있어도 수행 가능 - 동적 계획법의 원리를 이용해 알고리즘에 접근	$O(V^3)$

플로이드-워셜 알고리즘의 핵심 이론

• A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 또한 최단 경로

• 위 그림에서 1번 노드에서 5번 노드로 가는 경로 중 색칠된 경로가 최단 경로라고 할 때
• 1->4 경로와 4->5 경로 또한 최단 경로라는 것

플로이드-워셜 점화식

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

• $D[S][E]$는 S 노드에서 E 노드 까지의 최단 경로 배열
• 이 때 S==E인 최단 경로 배열은 0으로 초기화, 나머지는 INF로 초기화
  • 자기 자신에게 가는 경로를 의미하기 때문

플로이드-워셜 단계

1. 최단 경로 배열을 선언하고 초기화

• $D[S][E]$는 노드 S에서 E까지의 최단 경로 배열
• 만약 S와 E가 같으면 0, 그 외에는 INF로 초기화

2. 최단 경로 배열에 그래프 데이터 저장

• 출발 노드 S에서 도착 노드 E로 가는 가중치로 업데이트

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

• $D[S][E] = min(D[S][E], D[S][K] + D[K][E])$로 최단 경로 배열 업데이트

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