플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드 워셜 알고리즘이란? 모든 노드간의 최단 거리를 구하는 알고리즘으로 음수 가중치 엣지가 있어도 수행할 수 있으며 동적 계획법(DP)의 원리를 이용해 알고리즘에 접근합니다.

그래프는 모든 노드에서 모든 노드의 거리를 나타낼 수 있는 인접행렬로 표현합니다. 동적 계획법(DP)적 접근 위 그래프에서 시작 노드에서 끝 노드까지 가는 최단 거리는 7(start -> T2 -> T1 -> end) 입니다.

그렇다면 T1까지의 최단 거리는 몇일까요? 당연히 start -> T2 -> T1 으로 5입니다.

즉 동적 계획법을 적용하였을 때 시작 노드부터 도착지 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 경유지 노드가 존재한다면 그 경유지 노드 까지도 결국 최단 거리라는 것을 이해할 수 있습니다. 이를 통한 점화식 도출 DP[S][E] = min(DP[S][E], DP[S][T] + DP[T][E]) 출발 노드 S 에서 E 까지 가는 최단거리를 S에서 임시 노드 T 까지의 거리...