들어가기에 앞서
하단의 참고한 자료를 바탕으로 개인의 생각을 정리한 글이므로 오류가 있을 수 있습니다.
오류에 대한 피드백은 언제든지 환영합니다. 부디 댓글로 알려주시길 바랍니다. 감사합니다.
플로이드-워셜(floyd-warshall) 알고리즘이란?
플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다.
이 알고리즘의 핵심원리는 A노드에서 B노드까지 최단경로를 구했을 때, 해당 경로 위에 C노드가 존재한다면 그 노드를 이루는 부분 경로 역시 최단 경로라는 것입니다. 즉, 전체 경로의 최단경로는 부분 경로의 최단 경로의 조합으로 이뤄진다는 뜻입니다.
이는 부분적인 경로를 이용하여 전체 경로를 구한다는 점에서 동적계획법의 bottom-up 형태를 연상할 수 있습니다. bottom-up 형태의 동적계획법은 점화식을 세워 문제를 해결하는데, 플로이드 워셜 알고리즘의 경우에는 다음과 같이 점화식을 도출할 수 있습니다.
distance[start][end] = Math.min(distance[start][end], distance[start][mid] + distance[mid][end])
또 다른 주요 특징으로는 다익스트라 알고리즘과는 달리 음수 가중치 에지가 있어도 수행가능하다는 점입니다.
구현
플로이드-워셜 알고리즘의 구현 방법은 다음과 같습니다.
1. 배열 선언 및 초기화
인접행렬 형태로 distance배열을 초기화합니다. distance[start][end]는 start노드에서 end노드까지의 최단 거리를 저장하는 배열입니다. start와 end가 같은 경우에는 자기 자신에게 가는 거리이므로 0, 나머지는 문제에서 제시한 가중에 해당하는 값을 저장하고, 존재하지 않을 경우 충분히 큰 값을 저장합니다.
2. 점화식으로 배열 업데이트
앞서 구했던 점화식으로 3중 for문 형태로 반복하면서 값을 업데이트합니다. 업데이트가 완료된 배열은 모든 노드간의 최단거리를 나타냅니다.
// n: 그래프의 노드 수
// distance[][]: 그래프의 인접 행렬 (경로가 없는 경우 무한대로 초기화)
// M: 경유 노드
for M from 1 to n :
for A from 1 to n :
for B from 1 to n :
// A에서 B로 가는 경로를 직접 가는 것과 M을 거치는 것 중 더 짧은 경로를 선택
distance[A][B] = min(distance[A][B], distance[A][M] + distance[M][B])
JavaScript
복사
위 수도코드를 보면 알 수 있듯이 시간복잡도는 O(N^3)으로 매우 느린편입니다. 이에 따라 이 알고리즘을 통해 구현해야하는 문제는 노드의 개수가 다른 그래프 관련 문제보다 적다는 것을 의미한다고 볼 수 있습니다.
참고
•
Do it 코딩테스트
•
다빈치 코딩알고리즘 - 동적계획법
