인생자취

1. 들어가기 지난 글에서는 경로의 가중치가 음수로 부여된 경우에 사용되는 벨만-포드 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 사용하는 알고리즘이긴 하나, 모든 노드간 최단 거리를 탐색하는 알고리즘인 플로이드-워셜(Floyd-Warshall)에 대해 알아볼 것이다. 2. 플로이드-워셜(Floyd-Warshall) 플로이드-워셜 알고리즘으 모든 정점의 쌍 사이에 최단 경로를 구할 수 있다. 다만, 음의 가중치의 순환(음수 사이클)이 없다는 가정 하에서 구할 수 있다. 모든 쌍의 최단 경로는 최단 경로의 부분 경로이므로, 경로의 부분 경로가 모여 곧 최단경로가 되는 형태이다. 그러므로 최단 경로를 구하는 상향식 접근방법이라 볼 수 있다. 플로이드-워셜 알고리즘은 모든 정점의 쌍..