플로이드-웨셜 알고리듬

💫 플로이드-웨셜 알고리듬 - Floyd-Warshall Algorithm

---

워셜이 먼저 만들었지만, 이를 개선한 플로이드가 더 네임드여서.

• 문제의 이해: 모든 쌍 최단경로 알고리듬
  • 모든 지점들 간의 최단 경로를 알려줌
  • 유형
    1. 단일 시작점 최단 경로 알고리듬을 여러 번 반복
       • i.e. 벨먼-포드 알고리듬을 n번 반복: Ɵ(n^2 e), 고밀도 그래프의 경우 최대 Ɵ(n^4)
    2. 플로이드-워셜 알고리듬(Floyd-Warshall algorithm)
       • 음의 가중치 간선을 허용하는 방향 그래프에서 모든 쌍 최단 경로를 Ɵ(n^3)에 찾음
       • 음의 사이클은 허용되지 않음
       • 기본 아이디어
         • 정점 V={1, 2, …, n}과 간선 E가 주어졌을 때 A와 B 두 정점간 최단 경로 길이
         • = 정점 {1, 2, …, n}에 속한 정점들을 가지고 만들 수 있는 최단 경로 길이
         • ≤ 정점 {1, 2, …, n-1}에 속한 정점들을 가지고 만들 수 있는 최단 경로 길이 (최단 경로가 n을 거치면 같고, Like 배낭문제)
         • …
         • ≤ 정점 {1, 2, …, k}에 속한 정점들을 가지고 만들 수 있는 최단 경로 길이
         • …
         • ≤ 정점 {1}에 속한 정점들을 가지고 만들 수 있는 최단 경로 길이
         • ≤ 정점 { }에 속한 정점들을 가지고 만들 수 있는 최단 경로 길이(아무 정점도 거치지 않음)
         • 주어진 문제의 크기가 가장 크고 점점 문제의 크기가 작아져서 가장 마지막에 있는 문제의 크기가 가장 작음 🡺 가장 작은 문제의 최적해로부터 점점 큰 문제의 최적해를 구할 수 있다면!!

모든 쌍 최단 경로는, 플로이드-워셜 알고리듬을 몰라도, 단일 시작점 최단 경로 알고리듬을 시작점을 다르게 n번 반복 시켜 풀 수는 있다. (n^4)
그런데 플로이드-워셜 알고리듬을 쓰면 n^3으로 풀 수 있다.

알고리듬.. 많이 알아야겠지?

• 문제의 순환적 정의
  • 최종 목표: 모든 정점들 간의 최단 경로
  • 최우선 목표: 모든 정점들 간의 최단 경로 길이
    • 정점 i에서 정점 j까지(i∼>j) 최단 경로 길이
    • = 정점 {1, 2, …, n}에 속한 정점들만 거치는 i∼>j의 최단 경로 길이 D_n(i, j)
    • = 다음 두 최단 경로 중 더 짧은 경로
      1. 정점 n을 안거치는/안쓰는 최단 경로
      • 정점 {1, 2, …, n-1}에 속한 정점들만 거치는 최단 경로
      • → D_n-1(i, j)
        1. 정점 n을 거치는/쓰는 최단 경로
      • 정점 i에서 정점 n을 거쳐 정점 j에 도달하는 최단 경로, i ~> n ~> j
      • i∼>n도 최단 경로로 이동하고 n∼>j도 최단 경로로 이동해야 하므로 D_n(i, n) + D_n(n, j)
      • 이때, i∼>n의 최단 경로는 중간에 정점 n을 거치지 않음 (정점 수 : n-1)
      • 이때, n∼>j의 최단 경로는 중간에 정점 n을 거치지 않음 (정점 수 : n-1)
      • → D_n(i, n) + D_n(n, j) = D_n-1(i, n) + D_n-1(n, j)
  • 일반화
    • 정점 {1, 2, …, k}에 속한 정점만 거치는 i∼>j의 최단 경로 길이 Dk(i, j)
    • = 다음 두 최단 경로 중 더 짧은 경로
      1. 정점 k를 안거치는/안쓰는 최단 경로
      • 정점 {1, 2, …, k-1}에 속한 정점들만 거치는 최단 경로
      • → D_k-1(i, j)
        1. 정점 k를 거치는/쓰는 최단 경로
      • i -{(1, 2, …, k-1)에 속한 정점}→ k -{(1, 2, …, k-1)에 속한 정점}→ j
      • i∼>k∼>j의 최단 경로
      • i∼>k와 k∼>j도 최단 경로로 이동해야 함: D_k(i, k) + D_k(k, j)
      • 이때, i∼>k의 최단 경로는 중간에 정점 k를 거치지 않음 (정점 수 : k-1)
      • 이때, k∼>j의 최단 경로는 중간에 정점 k를 거치지 않음 (정점 수 : k-1)
      • 🡺 D_k(i, k) + D_k(k, j) = D_k-1(i, k) + D_k-1(k, j)

D_n(i, j)는 D(n, i, j)로 써도 되긴하는데, 이렇게 되면 3차원 배열을 써야하고, 3차원 배열은 다루기 복잡하니까
상대적으로 다루기 쉬운 2차원 배열을 여러 개 만들어 쓰는 식으로 쓰기 위해 n을 아래첨자로 쓴다.
Like 배낭 문제

D_n(i, j) = Min { D_n-1(i, j), D_n-1(i, n) + D_n-1(n, j) }

D_n(i, j) =
if (k > 0) Min { D_n-1(i, j), D_n-1(i, n) + D_n-1(n, j) }
if (k == 0) (i, j)의 가중치

일반화시키면
D_k(i, j) = Min { D_k-1(i, j), D_k-1(i, k) + D_k-1(k, j) }

DP로 만든다 = 배열로 만든다

• DP
  • 최우선 목표: 정점 {1, …, n}에 속한 정점만 거치는 i∼>j의 최단 경로 길이 D_n(i, j)
  • 2차원 배열의 원소 D_k[i][j]에 D_k(i, j)의 값을 저장하고 필요할 때마다 재사용
  • 주어진 그래프는 비용 인접 행렬 W에 저장
  • 중간에 아무 정점도 거치지 않는 최단 경로 길이를 저장하기 위한 배열 D₀에서부터 시작하여 차례로 배열 D₁, D₂, …, D_n을 생성하는 단계를 거침(배열 D₀은 인접 행렬 W 와 동일)
  • 배열 D_k에는 최단 경로 길이만 저장 🡺 최종 목표인 최단 경로를 기억할 배열이 필요
    • D_k[i][j]가 변경되면 k를 배열 V_k[i][j]에 저장. 즉 i∼>j의 최단 경로가 k를 경유한다면 V_k[i][j]= k로 지정
    • Vn[i][j]부터 거꾸로 조사해 내려가면 i∼>j의 최단 경로가 어떤 정점들을 경유하는지 알 수 있음

D_k[i][j] =
if (k > 0) Min { D_k-1[i][j], D_k-1[i][k] + D_k-1[i][k] }
if (k == 0) [i][j]의 가중치

• 알고리즘
  • 여러 개의 배열을 사용하지 않고 하나의 배열만 사용해서 계속 덮어쓰기를 반복
  • 임의의 D_k[i][j]를 구하기 위해 사용되는 D_k-1[i][k]는 D_k[i][k]와 같고 D_k-1[k][j]는 D_k[k][j]와 같으므로 이 두 값은 D_k를 구하는 k 번째 반복문 내에서는 절대로 변경되지 않기 때문
  • D_{k을 구하기 위해 참고하는 값은 Dk-1[k][?] 나 Dk-1[?][k], Dk-1의 k행과 k열의 요소들 뿐}
  • 복잡도: Ɵ(n³)

void FloydWarshallDP(int d[][MAX], int n)
{
	int V[MAX][MAX] = {0};
	for (int k = 1; k <= n; k++) // 각 정점에 대해 : n
		for (int i = 1; i <= n; i++) // 행 : n
			for (int j = 1; j <= n; j++) // 열 : n
				if (D[i][k] + D[k][j] < D[i][j]) // k를 경유하는 거리가 더 짧으면
				{
					D[i][j] = D[i][k] + D[k][j]; // 거리
					V[i][j] = k; // 경유
				}

	// 복잡도 : n * n * n
}

💫 이행적 폐쇄 문제

---

(추이적 폐포)(transitive closure)

🫧 이행적 관계

R이 집합 S에 대한 관계라 할 때 모든 a,b,c ∈ S에 대해 (a,b)∈R이고 (b,c)∈R이면 (a,c)∈R을 만족하는 경우 R을 이행적 또는 이행적 관계라고 한다.

🫧 이행적 폐쇄

R이 집합 S에 대한 관계라 할 때 관계 R을 포함하는 가장 작은 이행적인 관계를 R의 이행적 폐쇄라고 한다.

🫧 _

• 문제: 그래프의 각 정점 사이에 경로가 존재하는가?
  • 이행적 폐쇄 관계 R을 방향 그래프로 나타낸다면
  • a에서 b로 경로가 존재하고 b에서 c로 경로가 존재하면 반드시 (a, c)∈R
  • ∴ 관계에서의 이행적 폐쇄를 구하는 문제 ≡ 그래프의 정점사이에 경로가 존재하는지 여부를 조사하는 문제
  • 🡺 플로이드-워셜의 알고리즘을 이용하여 해결