모든 쌍 최단 경로

모든 쌍 최단 경로 문제는 그래프의 각 노드에서 다른 모든 노드로의 최단 경로를 동시에 계산한다. 단, 각 노드 쌍 간에 경로가 존재해야 한다. 단순한 접근 방식으로는 각 노드에서 다른 모든 노드로의 단일 출발지 최단 경로를 계산할 수 있다. 이 경우 계산되는 최단 경로의 수는 O(V^2)로 제한되며, 여기서 V는 그래프의 정점 수를 의미한다. 단일 출발지 최단 경로(SSSP)도 O(V^2)로 제한되기 때문에, 이 단순한 접근 방식의 총 실행 시간은 O(V^4)가 된다.

그러나 그래프의 인접 행렬에 동적 프로그래밍을 적용하면 Floyd-Warshall 알고리즘을 사용해 O(V^3)의 실행 시간을 달성할 수 있다. Floyd-Warshall 알고리즘은 인접 행렬을 순회하며, 각 시작(i)과 끝(j) 정점 쌍에 대해 현재 두 정점 간의 거리가 다른 정점(k)을 거치는 경로보다 큰지 확인한다(경로 i ~> k와 k ~> j가 존재하는 경우). 이 알고리즘은 각 정점 k에 대해 인접 행렬을 순회하며 모든 쌍 (i, j)에 대해 비교를 수행한다. 따라서 각 k에 대해 새로운 인접 행렬 D(k)가 생성되며, 여기서 각 값 d(k)[i][j]는 다음과 같이 정의된다:

여기서 w[i][j]는 그래프의 원래 인접 행렬에서 정점 i와 정점 j를 연결하는 간선의 가중치를 나타낸다.

알고리즘이 각 개선된 인접 행렬과 이전 행렬을 메모이제이션하면 공간 복잡도는 O(V^3)이 된다. 그러나 최신 개선 사항만 메모이제이션하면 공간 복잡도를 O(V^2)로 최적화할 수 있다. 경로를 재구성하는 작업은 재귀적 절차로, O(V) 시간과 O(V^2) 공간이 필요하다.

예제

다음과 같은 가중치가 있는 방향 그래프가 있다.

이 그래프의 인접 행렬 표현 w는 다음과 같다.

최단 경로 가중치 계산

알고리즘 초기 단계에서 D(0)는 w와 동일하지만, 비교 함수를 적용하기 위해 다음과 같은 예외가 적용된다:

  1. 연결 경로가 없는 정점의 경우 ø를 ∞로 대체한다.
  2. 대각선 요소는 모두 0으로 설정한다.

위 그래프에 플로이드-워셜 알고리즘을 적용해 도출한 모든 인접 행렬은 다음과 같다:

마지막 행렬이 최종 결과이며, 각 시작 정점과 도착 정점 쌍에 대해 최단 경로의 총 가중치를 나타낸다. k = 2 단계에서 오른쪽 상단 값을 2에서 -4로 변경하는 비교 과정은 다음과 같다:

k = 2, i = 0, j = 3
d(k-1)[i][j] => d(1)[0][3] = 2
d(k-1)[i][k] => d(1)[0][2] = 1
d(k-1)[j][k] => d(1)[2][3] = -5

따라서 min(2, 2 + -5) => min(2, -4)를 계산하면 d(2)[0][3] 요소의 새로운 가중치로 -4가 도출된다. 이는 이전 단계에서 1 ~> 4까지의 최단 경로가 1 -> 2 -> 4로 총 가중치가 -2였지만, 이후 1 -> 3 -> 4 경로가 더 짧은 총 가중치 -4를 가진다는 것을 발견한 것을 의미한다.

최단 경로 재구성

이 알고리즘은 모든 노드 쌍 간의 최단 경로 길이만 찾는다. 최단 경로를 재구성하려면 별도의 기록 구조를 유지해 선행 노드의 인덱스를 추적해야 한다. 위 그래프의 각 단계에서 선행 행렬은 다음과 같다:

프로젝트 구조

제공된 xcworkspace는 플레이그라운드에서 작업할 수 있도록 구성되어 있다. 이 워크스페이스는 xcodeproj에서 APSP 프레임워크 타겟을 임포트한다. 시작하려면 프레임워크 타겟을 빌드한 후 플레이그라운드를 다시 실행하면 된다. xcodeproj에는 테스트 타겟도 포함되어 있다.

프레임워크 내부에는 다음과 같은 내용이 있다:

TODO

참고 자료

Cormen, Leiserson, Rivest, Stein의 Introduction to Algorithms, Third Edition 25장
https://mitpress.mit.edu/books/introduction-algorithms

Swift Algorithm Club을 위해 Andrew McKnight가 작성