20. floyd warchall algorithm [10 1주차]

20. Floyd Warchall Algorithm [10-1주차]

2024년 1월 14일 일요일

오전 2:51

<All-Pairs Shortest Path 문제>

모든 쌍에 대해 shortest path를 구하는 문제.

Dijkstra 알고리즘의 시간복잡도는 O(ElogN)으로, 간선의 개수가 많을 경우 최대 O(N²logN)이 걸린다.

Dikstra를 N번 돌리면 O(N³logN) 이 걸린다. 이보다 더 빠른 방법이 있을까?

<Floyd Warshall Algorithm>

O(N³)시간에 답을 구할 수 있다.

D[k][i][j]를 계산할 것이다. [i][j]는 모든 노드 쌍을 의미한다.

D[k][i][j]는 i번 노드로부터 j번 노드로의 제일 짧은 경로 길이이다. 단, 1번부터 k번 노드만 거쳐가며, k+1 ~ N번 노드는 중간에 포함되지 않는다. i, j번 노드는 k보다 커도 무조건 포함됨.

k=0 일 때는 거쳐갈 수 있는 노드들의 집합이 공집합이다. 이때 i번 노드와 j번 노드가 직접 연결되어 있는 경우만 고려하게 된다.

D[k-1][i][j]이 계산되었다고 가정되고 D[k][i][j]를 계산하자.

i부터 j까지의 가능한 모든 경로를 k번 노드가 포함되는 경우와 k번 노드가 포함되지 않는 경우로 나누고, 각 집합에서 가장 작은 경로를 찾아보자. k번 노드가 포함되지 않는 집합에서의 가장 작은 경로는 이미 구해진 D[k-1][i][j]이다.

k가 포함되는 최단 경로는 k가 무조건 한번 나와야 한다. (두 번 나오는 경우는 사이클이 생겨 한번 나오는 경우보다 경로가 클 수밖에 없다)

따라서 k가 포함되는 최단 경로는 i에서 k로의 최단 경로와 k에서 j로의 최단 경로로 구성된다. 그런데 i와 k, k와 j 사이에는 k가 존재하지 않으므로, 나누어진 두 최단 경로는 k-1 배열에 저장된 값이다.

따라서 다음 식이 성립한다.

D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j] )

<메모리를 적게 쓰는 방법>

삼차원 배열을 사용하므로 메모리가 많이 든다. 코드를 보면, D[k][][]를 구할 때 D[k-1][][]만 사용한다. 따라서, 삼차원 배열을 쓰는 대신 이차원 배열 두 개만 번갈아 쓰면서 메모리를 절약할 수 있다.

2차원 배열 하나만 쓰는 방법도 있다.

위 코드를 보면, D[][]배열 하나에 Floyd Warshall 알고리즘을 적용하고 있다. 이때 걱정되는 부분은, D[k]와 D[k-1] 두 배열을 한 배열에 저장하게 되면서, D[k]를 계산하는 과정에서 D[k-1]의 값이 아닌 D[k]의 값을 가져오게 되는 경우이다. 이런 문제가 발생하지 않는다는 것을 증명해 보자.

D[k-1][i][j]의 값은 D[k][i][j]를 계산한 뒤에 업데이트가 되므로, D[k][i][j]를 계산하는 시점에는 업데이트가 안 되어 있는 것이 분명하다.

D[k-1][i][k], D[k-1][k][j] 의 값은 어떨까?

i부터 k까지의 경로 안쪽에는 k번 노드가 없다. 따라서 D[k][i][k] = D[k-1][i][k] 이므로, 값이 업데이트가 되어도 이 부분은 달라지지 않는다. 마찬가지로 D[k][k][j] = D[k-1][k][j] 이다. 따라서 2차원 배열 하나만 써도 문제가 없다.