10강. 그래프 (3)

1. 벨만-포드 알고리즘

• 단일 출발점 최단 경로를 구하는 알고리즘
  • 음의 가중치를 갖는 간선이 존재하는 경우에도 처리 가능
  • 단, 음의 사이클이 없는 경우에만 동작함
• G=(V, E)에서 |V|=n일 때, 단계적으로 최단 경로를 구해 나가는 방식
  • 간선을 최대 1개 사용하는 최단 경로
  • 간선을 최대 2개 사용하는 최단 경로
  • …
  • 간선을 최대 (n-1)개 사용하는 최단 경로
• 수행 과정
  • 초기화
    • 출발점 s의 거리 d[s] = 0
    • 나머지 모든 정점 v의 거리 d[v] = ∞
  • for i ← 1 to |V| - 1
    • 모든 간선을 한 번씩 조사하면서 거리값 조정 여부 결정
    • d[v] ← min{ 기존 거리 d[v], 간선 ⟨u, v⟩를 지나는 경우의 거리 d[u] + w }
    • 전 단계에서 거리값 d[ ]의 조정이 발생한 정점에 부수된 간선만 조사하는 방식으로 최적화 가능

2. 벨만-포드 알고리즘 성능과 특징

// 입력: G = (V, E), s : 시작 정점  
// 출력: d[ ] : s로부터 다른 모든 정점으로의 최단 경로의 길이  
//       prev[ ] : 최단 경로를 만드는 선행 정점
        
Bellman_Ford(G, s) {

 // 초기화
  for (모든 정점 v ∈ V) { // O(|V|)
    d[v] = ∞;
    prev[v] = NULL;
  }
  
  d[s] = 0;
  
  // 반복  O(|V||E|)
  for (i = 1; i < n; i++) { // O(|V|)
    for (모든 간선 (u, v) ∈ E) { // O(|E|)
      if (d[v] > d[u] + W(u, v)) {
        d[v] = d[u] + W(u, v);
        prev[v] = u;
      }
    }
  }
  return (d[ ], prev[ ]);
}

• 성능 : O(|V||E|)
• 음의 가중치를 갖는 간선이 있는 경우
  • 데이크스트라 알고리즘 적용 불가
  • 벨만-포드 알고리즘 적용 가능
    • 단, 음의 사이클이 존재하면 적용 불가
• 음의 가중치를 갖는 간선이 없는 경우
  • 데이크스트라 알고리즘 → O((|V|+|E|) log|V|) ⇒ 바람직
  • 벨만-포드 알고리즘 → O(|V||E|)

3. 플로이드 알고리즘

• 모든 쌍 최단 경로 알고리즘
  • "Floyd-Warshall 알고리즘"
  • 가정
    • 경로의 길이가 음의 사이클이 존재하지 않음
  • 적용 기법
    • 동적 프로그래밍 방법
  • 경유할 수 있는 정점의 범위가 1인 경로부터 시작해서 |V|( 정점의 개수 )인 경로까지 하나씩 정점의 범위를 늘려 가면서 모든 정점 간의 최단 경로를 한꺼번에 구함
• 인접 행렬 표현 활용
  • Dᵏ = ( dᵢⱼᵏ ) ( k = 0, 1, ..., |V| )
    • dᵢⱼᵏ의 의미
      • 정점 번호가 k 이하인 정점만을 경유하는, 정점 i에서 j까지의 최단 경로 길이
  • D⁰ = ( dᵢⱼ⁰ = w(i, j) ) → D¹ → D² → ... → D⁽|V|⁾ ( 최종 결과 )
  • 점화식
    • dᵢⱼᵏ = min( dᵢⱼᵏ⁻¹, dᵢₖᵏ⁻¹ + dₖⱼᵏ⁻¹ )
      • dᵢⱼᵏ⁻¹ : 기존 거리
      • dᵢₖᵏ⁻¹ + dₖⱼᵏ⁻¹ : 정점 k를 경유하는 경우의 거리
• dᵢⱼᵏ⁻¹ 과 dᵢⱼᵏ 의 관계
  • dᵢⱼᵏ⁻¹ : 정점 1부터 k−1까지만 경유한 i → j의 최단 경로
  • dᵢₖᵏ⁻¹ + dₖⱼᵏ⁻¹ : 정점 k를 추가로 경유한 i → j 경로
  • 즉, dᵢⱼᵏ = min( dᵢⱼᵏ⁻¹, dᵢₖᵏ⁻¹ + dₖⱼᵏ⁻¹ )
    • 기존 거리와, 정점 k를 경유한 거리 중 더 짧은 것 선택

4. 플로이드 알고리즘 성능과 특징

// 입력: G = (V, E), 인접 행렬 A[1..n][1..n]
// 출력: D[][] = 모든 정점 쌍 간의 최단 경로의 길이

Floyd(G) {
		// 초기화 성능 : O(n²)
    for (i = 1; i <= n; i++) { // D⁽⁰⁾ = ( dᵢⱼ⁽⁰⁾ = wᵢⱼ )
        for (j = 1; j <= n; j++) {
            D[i][j] = A[i][j];
        }
    }

		// 성능 : O(n³)
    for (k = 1; k <= n; k++) { // D⁽ᵏ⁾: 경유하는 정점 k 
        for (i = 1; i <= n; i++) { // Dᵢⱼ
            for (j = 1; j <= n; j++) {
                if (D[i][j] > D[i][k] + D[k][j]) { // 경유하는 경우
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }

    return D;
}

• 성능 : O(n³) → n=|V|
• 특징
  • 동적 프로그래밍 방법을 적용한 알고리즘
    • dᵢⱼᵏ = min( dᵢⱼᵏ⁻¹, dᵢₖᵏ⁻¹ + dₖⱼᵏ⁻¹ )
  • 데이크스트라 알고리즘으로 모든 쌍 최단 경로를 구할 수 있음
    • 각 정점에 대해서 반복적으로 적용해서 해결 가능 → O(|V|³)
    • 플로이드 알고리즘이 더 간단하므로 빠르게 수행
    • |E| ≪ |V|²인 경우에는 데이크스트라 알고리즘의 반복 적용이 더 효과적
  • P[1..n][1..n]을 활용하면 최단 경로 자체를 구할 수 있음
    • P[i][j] = k if dᵢⱼᵏ⁻¹ > ( dᵢₖᵏ⁻¹ + dₖⱼᵏ⁻¹ ) ( 정점 k를 경유하는 경우 )

5. 네트워크 플로 문제

• 주어진 네트워크에 대해서 플로우를 최대로 하는 값을 찾는 문제
  • 소스에서 싱크로 보낼 수 있는 플로 값을 최대로 하는 문제 → "최대 플로 문제"
• 네트워크 N = (V, E, s, t, c)
  • 방향 그래프 G = (V, E)
  • s → 소스 ( 시작점, 진입차수가 0인 정점 )
  • t → 싱크 ( 도착점, 진출차수가 0인 정점 )
  • c → 간선의 가중치 → 간선의 용량( capacity )
  • c(u, v) → 간선 ⟨u, v⟩를 통해 보낼 수 있는 최대의 양/값
• 플로 f: E → R⁺
  • 간선의 용량 중에서 실제 사용하고 있는 양/값
  • 용량 제약 조건
    • 모든 ⟨u, v⟩ ∈ E에 대해서 0 ≤ f(u, v) ≤ c(u, v)
    • 임의의 간선의 플로는 항상 0보다 크거나 같고, 해당 간선의 용량을 초과하지 못함
  • 플로 보존 제약 조건
    • 모든 v ∈ V - {s, t}에 대하여 ∑ f(u, v) = ∑ f(v, w)
    • 소스/싱크를 제외한 모든 정점에 대해서 어떤 정점으로 들어오는 양과 나가는 양은 동일
• 플로 값( 총 플로 ) F
  • F = ∑ f(s, v) = ∑ f(w, t)
  • 소스에서 나가는 플로의 합 = 싱크로 들어오는 플로의 합

6. 포드-풀커슨 알고리즘

• 최초로 제시된 가장 기초적인 해결 방법 ( by Ford & Fulkerson )
  • 단순히 플로 값을 증가시킬 수 있는 모든 경우의 수를 탐색해서 적용
  • 종료가 보장되지 않음 → 에드몬즈-카프 알고리즘으로 발전
• 모든 간선의 플로를 0으로 둔 상태에서 시작해서 증가 경로가 더 이상 존재하지 않을 때까지 반복적으로 경로를 찾아서 최대 플로 값을 구하는 방법
• 증가 경로 ( augmenting path )
  • 소스에서 싱크까지 더 많은 플로를 보낼 수 있는 경로
  • 경로상의 간선은 네트워크 N의 간선 방향과 일치하지 않을 수 있음
    • 순방향( forward ) 간선
      • 간선 <u, v>가 N의 간선의 방향과 같은 경우
    • 역방향( backward ) 간선
      • 간선 <u, v>가 N의 간선의 방향과 다른 경우
      • <v, u>∈E와 방향이 반대인 간선 → <u, v>∉E인 가상의 간선
      • c(u, v) = 0, f(u, v) = -f(v, u)
        • 간선 (u, v)의 용량은 0이다.
        • 흐름 함수 f는 방향에 대해 반대 값을 갖는다
          • 즉, 한 방향(u → v)의 흐름은 반대 방향(v → u)의 음수이다.
      • 남아 있는 모든 가능한 경로를 더 찾아낼 수 있게 하는 포드-풀커슨 방법의 핵심
• 잔여 용량 r(u, v)
  • 간선 <u, v>에서 추가로 플로를 증가시킬 수 있는 여유 용량
    • 순방향 간선
      • r(u, v) = c(u, v) - f(u, v)
      • 증가시킬 수 있는 양/값
    • 역방향 간선
      • r(v, u) = c(v, u) - f(v, u) = c(v, u) - (-f(u, v)) = 0 + f(u, v) = f(u, v)
      • 원래 간선에 부여된 플로를 줄일 수 있는 양/값
• 증가 경로의 여유량 ∆
  • ∆ = min{ r(u, v) | 경로상의 존재하는 간선 <u, v> }
    • 경로에 포함된 모든 간선의 잔여 용량 중 최소값
      • 해당 경로를 사용해서 증가시킬 수 있는 플로 값

7. 포드-풀커슨 알고리즘 성능과 특징

Ford_Fulkerson ( N ){
	모든 간선의 플로 f를 0으로 초기화;
	
	// 최대 유량 F에 도달하기 위해 최소 1씩 증가한다면 최대 F번 반복 (용량이 정수인 경우)
	while ( 증가 경로 p가 존재 ) {
		 // 잔여 용량 중 최소값
		 ∆ = min{ r(u, v) | p에 존재하는 <u, v> }
		 
		// DFS / BFS 사용 시 시간복잡도: O(|E| * F)
		for ( 증가 경로 p상의 모든 간선 <u, v> ) {
			if ( <u, v>가 순방향 간선 ) f(u, v) += ∆; // 플로 증가
			else f(u, v) -= ∆; // 역방향 간선 → 플로 감소 
		}
	}
	𝐹 = ∑𝑤∈𝑉 𝑓(𝑤,𝑡) ; // 싱크로 들어오는 모든 간선의 플로의 합
	return (F);
}

• 성능 : O(|E|F)
• 문제점
  • 용량으로 무리수를 사용 → 알고리즘의 종료가 보장되지 못함
  • 용량 M이 매우 큰 값이면 비효율적
    • 증가 경로 s-1-2-t와 s-2-1-t를 각각 M번 찾음 → F = 2M
• 특징
  • 증가 경로의 선택은 DFS 또는 BFS 적용
    • 포드-풀커슨 알고리즘 ➝ 기본적으로 DFS를 적용하여 증가 경로 선택
      • 에드몬즈–카프 알고리즘 ➝ BFS 적용, O(|V||E|²), 포드–풀커슨의 문제 해결
  • 커트 cut
    • 커트 ➝ (S ; T) ∪ (T ; S)
      • S ; T : S의 정점에서 T의 정점으로 향하는 간선의 집합
      • T ; S : T의 정점에서 S의 정점으로 향하는 간선의 집합

8. 정리하기

• 벨만–포드 알고리즘
  • 음의 가중치를 갖는 간선이 존재해도 적용할 수 있는 단일 출발점 최단 경로 알고리즘
  • O(|V||E|)
• 플로이드 알고리즘
  • 모든 정점 쌍 간의 최단 경로, 동적 프로그래밍 방법
  • 경유할 수 있는 중간 정점의 범위를 하나씩 늘려가는 방식
  • O(|V|³), 최단 경로 자체를 구하는 경우에는 P[i][j]에 경유하는 중간 정점을 저장
• 포드–풀커슨 알고리즘
  • 네트워크 플로 문제 → 네트워크에 대해서 소스에서 싱크로 보낼 수 있는 최대 플로 값을 구하는 문제
  • 포드–풀커슨 방법 → 증가 경로가 더 이상 존재하지 않을 때까지 반복적으로 찾아서 플로를 증가시키는 방법, O(|E|F)
  • 순방향 간선, 역방향 간선, 잔여 용량, 증가 경로의 여유량, 컷트 등 사용