All-Pairs Shortest Path

• Give a Weighted Graph
• Find the shortest path between all possible pairs of nodes
• One option: run dijkstra N times
• Time complexity?

다익스트라는 src가 고정되어 있지만, 이번에는 모든 쌍에 대해 shortest path를 구해보자.

다익스트라 알고리즘의 시간복잡도는 O((m+n)logn) (m은 edge의 개수, n은 node의 개수)이다. O(m+n) == O(m)이기 때문에 결국 O(mlogn)이고, 입력을 읽는데 O(m+n)의 시간이 걸리기 때문에 이보다는 빠를 수 없다.

그러면 다익스트라를 N번 시행해 모든 쌍들의 shortest path를 구하면 아마도 O(n(m+n)logn)의 시간이 걸릴 것이다.

모든 쌍의 shortest path를 구하는 알고리즘의 시간 복잡도는 O(n^3)이다. edge의 개수 m의 최댓값은 n^2이기 때문에 m이 클 경우는 둘이 비슷한 시간이 걸리나 m 값이 작은 경우에는 다익스트라를 쓰는 것이 낫다.

그래도 O notation으로 보이는 것보다 빠르기 때문에 자주 사용한다. 생각보다 빠름! 그래서 알고리즘이 따로 있다

Floyd-Warshall Algorithm

• Idea
  • (Nodes are numbered from 1 to N)
  • Find the shortest path from (all possible) i to j going through nodes in {1, 2, 3, …, k}
  • Do the above by increasing k from 0 to N

1번부터 k번 노드까지만 거칠 수 있는 shortest path를 구함. 이때 k=3이라면 1, 2, 3번 노드를 무조건 다 거쳐야 하는 것이 아니라 {1, 2, 3} 노드들 중에서만 골라서 거칠 수 있다. 그리고 k를 하나씩 증가시킨다.

k=0일 때: direct edge밖에 없으므로 노드 i, j 간의 direct edge가 없는 경우 답은 ∞이다.

k=1일 때: 1번 노드를 무조건 거쳐야 한다는 것이 아니라, 1번 노드를 방문해도 될 때, i번 노드에서 j번 노드까지의 최단 경로를 구하는 것이다.

1번 노드를 방문하는 것보다 direct로 갈 때의 비용이 작으므로 답은 여전히 10이다.

k=2일 때:

2번 노드가 추가되었다고 해서 1번 노드를 사용하지 않는 것도 아니고, 이런식으로 하면 노드가 하나 더 추가할 때마다 너무 복잡해진다.

A bit more Detail

• D[k][i][j] will contain the desired shortest path length
• Calculate D[k][i][j] from D[k-1][i][j]
• Initial values will be in D[0][i][j]

0 ≤ k ≤ n, 1 ≤ i ≤ n, 1 ≤ j ≤ n이므로 계산하는 값의 개수가 N^3개인 것을 알 수 있다. 전체 시간복잡도가 O(N^3)이므로 하나의 값을 상수 시간에 해야 하면 된다.

Definition
D[k][i][j]: {1, 2, 3, ..., k}만 거쳐 i에서 j로 가는 shortest path의 길이

k=0일 때: D[0][i][j]는 edge값이므로 direct edge인 W[i][j]이다.

k=N일 때: {1, 2, ..., N}이므로 결국 우리가 최종적으로 구하고자 하는 답이다.

Computing D[k][i][j] form D[k-1][i][j]

• Shortest path from i to j using nodes in {1, 2, …, k}
  • May use node k
  • Or may not use node k
  • The shorter of the two above is the answer

1. 노드 k를 반드시 방문한 path 중 가장 짧은 것을 찾고,
2. 노드 k를 방문하지 않은 path 중 가장 짧은 것을 찾아

둘 중 더 작은 것을 답으로 택한다.

• 노드 k를 반드시 방문하는 경우
  • i에서 j로 가는 shortest path에는 같은 노드가 두 번 이상 나올 수 없다. 그래서 i번 노드로부터 k번 노드까지 이동할 때에는 {1, 2, …, k-1}, k번 노드에서 j번 노드까지 이동할 때는 {k+1, …, j}이므로 D[k][i][j] = D[k-1][i][k] + D[k-1][k][j]

• 노드k를 방문하지 않는 경우
  • path 중 가장 짧은 것의 길이는 D[k-1][i][j]이다.

따라서 D[k][i][j] = min(D[k-1][i][k] + D[k-1][k][j], D[k-1][i][j])이다.

Code

int D[n+1][n+1][n+1];

int F(int W[n+1][n+1], int n) { // weight가 input으로 들어옴
	// init
	for (i = 1; i <= n; i++) {
		for(j = 1; j <= n; j++) {
			D[0][i][j] = W[i][j]; // k가 0인 경우 (direct edge)
		}
	}
	
	// k를 하나씩 증가시킴
	for(k = 1; k <= n; k++) {
		for (i = 1; i <= n; i++) {
			for(j = 1; j <= n; j++) {
				D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k]+D[k-1][k][j]);
			}
		}
	}
}

근데 실제로 구현 사례를 찾아보면 D가 3차원 배열이 아니라 2차원 배열일 것이다.

이제 메모리를 줄여보자.

Use Less Memory #1

위의 코드에서부터 알 수 있듯이, k번째를 계산할 때 k-1번의 결과를 가지고 계산하지 그 앞의 값은 사용하지 않고 관심도 없다. 또한 최종 정답도 D[n][i][j]이기 때문에, 앞에서부터 계산된 값을 다 갖고 있을 필요가 없다! 그러니까 배열의 row가 두 개만 있고 계속 덮어쓰면 된다.

int D[2][n+1][n+1];

int F(int W[n+1][n+1], int n) { // weight가 input으로 들어옴
	// init
	for (i = 1; i <= n; i++) {
		for(j = 1; j <= n; j++) {
			D[0][i][j] = W[i][j]; // k가 0인 경우 (direct edge)
		}
	}
	
	// k를 하나씩 증가시킴
	for(k = 1; k <= n; k++) {
		for (i = 1; i <= n; i++) {
			for(j = 1; j <= n; j++) {
				D[k % 2][i][j] = min(D[(k-1) % 2][i][j], D[(k-1) % 2][i][k]+D[(k-1) % 2][k][j]);
			}
		}
	}
}

그러나 2차원 배열로도 가능하다!

Use Less Memory #2

메모리를 더 줄이는 방법은 2차원 배열로 구현하는 것이다. 그러면 지금 사용하는 값이 D[k-1][i][j]인지 D[k][i][j]인지 몰라 값이 섞이는 문제가 발생하지 않을까?

다행히도 k-1일 때와 update되어 k일 때의 값은 항상 같기 때문에 그렇지 않다.

Proof 1 (Definition)

D[k-1][i][k]를 ①, D[k][i][k]를 ②라 하자. ①의 정의는 {1, 2, …, k-1}을 사용해 i에서 k로 가는 가장 짧은 길,
②는 정의는 {1, 2, …, k}를 사용해 i에서 k로 가는 가장 짧은 길이다. 그런데 shortest path란 같은 노드를 두 번 이상 방문할 수 없으므로 ②에서도 사용할 수 있는 노드들은 {1, 2, …, k}이지만 실제로는 중간에 k에 방문할 수 없다! 그래서 ①과 ②는 같은 값이다.

Proof 2 (Code)

D[k][i][k] = min(D[k-1][i][k], D[k-1][i][k]+D[k-1][k][k])이다. 그런데 k에서 k로 가는 shortest path의 길이는 언제나 0이므로 D[k-1][k][k]) == 0이고, D[k-1][i][k] == D[k-1][i][k]+D[k-1][k][k]이 된다.

따라서 D[k][i][k] = D[k-1][i][k]임을 확인할 수 있다.

int D[n+1][n+1];

int F(int W[n+1][n+1], int n) { // weight가 input으로 들어옴
	// init
	for (i = 1; i <= n; i++) {
		for(j = 1; j <= n; j++) {
			D[i][j] = W[i][j]; // k가 0인 경우 (direct edge)
		}
	}
	
	// k를 하나씩 증가시킴
	for(k = 1; k <= n; k++) {
		for (i = 1; i <= n; i++) {
			for(j = 1; j <= n; j++) {
				D[i][j] = min(D[i][j], D[i][k]+D[k][j]);
			}
		}
	}
}