알고리즘 10강 (그래프)

학습개요

1. 지난 시간에 이이서 이번 시간에도 그래프의 대표적인 응용문제로서, 최단 경로를 구하는 벨만-포드 알고리즘과 플로이드 알고리즘에 대해서 살펴보고, 네트워크 플로 문제와 이를 위한 가장 기본적인 형태의 포드-풀커슨 알고리즘에 대해서 학습한다.

 학습목표

1. 벨만-포드 알고리즘의 개념, 동작 그리고 특징을 이해하고 적용할 수 있다.
2. 플로이드 알고리즘의 개념, 동작, 그리고 특징을 이해하고 적용할 수 있다.
3. 네트워크 플로 문제의 정의, 용어 및 이를 위한 포드-풀커슨 알고리즘을 이해하고 적용할 수 있다.

 주요용어

1. 벨만-포드 알고리즘(Bellman-Ford algorithm)
   - 음의 가중치를 갖는 간선이 존재하는 그래프에 대해서도 단일 출발점 최단 경로를 구할 수 있는 방법
   - 간선을 1개부터 최대 (|V|-1)개까지를 사용하는 최단 경로를 단계적으로 구하는 방법
2. 플로이드 알고리즘(Floyd algorithm)
   - 동적 프로그래밍 방법을 적용하여 모든 정점 쌍 간의 최단 경로를 한꺼번에 구하는 알고리즘
3. 네트워크 플로 문제(network flow problem)
   - 주어진 네트워크에 대해서 소스에서 싱크로 보낼 수 있는 플로 값을 최대로 하는 문제(“최대 플로 문제”)
4. 포드-풀커슨 알고리즘(Ford-Fulkerson algorithm)
   - 모든 간선의 플로를 0으로 둔 상태에서 시작해서 증가 경로가 더 이상 존재하지 않을 때까지 반복적으로 경로를 찾아서 최대 플로값을 구하는 방법
5. 증가 경로(augmenting path)
   - 소스에서 싱크까지 더 많은 플로를 보내기 위한 경로
6. 커트(cut)
   - 소스와 싱크가 각각 서로 다른 집합에 속하도록 정점의 집합을 2개의 집합으로 나누었을 때 두 집합을 연결하는 간선의 집합

정리하기

1. 벨만-포드 알고리즘
   ⦁ 단일 출발점 최단 경로 알고리즘
   - 데이크스트라 알고리즘 → 음의 가중치를 갖는 간선이 있으면 적용 불가
   - 벨만-포드 알고리즘 → 음의 가중치를 갖는 간선이 존재하는 그래프에 대해서도 적용 가능 → 음의 사이클이 있는 경우에는 적용 불가
    ⦁ |V|=n인 G=(V,E)에서 간선을 1개부터 최대 (n-1)개까지를 사용하는 최단 경로를 단계적으로 구하는 방법 → 모든 간선을 한 번씩 조사하면서 기존 거리와 해당 간선을 지남으로써 결정되는 거리 중에서 작은 값으로 d[]를 조정하는 과정을 (n-1)번 반복 → 각 단계에서 모든 간선을 조사할 필요 없이, 실제로는 이전 단계에서 거리값이 조정된 정점에 부수된 간선만 조사하면 좀 더 효율적인 처리가 가능
    ⦁ 성능 → O(|V||E|)
    ⦁ 음의 가중치를 갖는 간선이 없는 경우에는 데이크스트라 알고리즘이 더 바람직
2. 플로이드 알고리즘
    ⦁ 모든 정점 쌍 간의 최단 경로를 구하는 문제
   - 경유할 수 있는 중간 정점의 범위가 1인 경로부터 시작해서 |V|인 경로까지 하나씩 정점의 범위를 늘려가면서 모든 정점 쌍 간의 최단 경로를 구함
   - 가정 → 경로의 길이가 음인 사이클이 그래프에 존재하지 않음
   - 동적 프로그래밍 방법이 적용됨
    ⦁ 성능 → O(|V|3)
    ⦁ 각 정점을 출발점으로 사용하여 데이크스트라 알고리즘을 반복적으로 적용해서도 해결 가능 → 플로이드 알고리즘이 더 효율적
    ⦁ |V|×|V| 크기의 배열 P[][]를 사용해서 최단 경로 자체를 구할 수 있음 → 정점 k를 경유하는 경로의 길이가 경유하지 않는 경로의 길이보다 더 짧으면 P[i][j]에 중간 정점 k를 저장해서 활용
3. 포드-풀커슨 알고리즘
    ⦁ 주어진 네트워크 N에 대해서 소스 s에서 싱크 t로 보낼 수 있는 플로 값 F를 최대로 하는 문제
   - 네트워크 N=(V,E,s,t,c)
   - G=(V,E) → 가중 방향 그래프
   - 용량 c → 간선의 가중치 → 간선을 통해 보낼 수 있는 최대의 양이나 값
   - 플로 f(u,v) → 간선 <u,v> 의 용량 중에서 실제 사용하고 있는 양/값 → 용량 제약 조건, 플로 보존 제약 조건
   - 플로 값 F → 소스에서 나가는 플로의 합 또는 싱크로 들어오는 플로의 합
    ⦁ 포드-풀커슨 알고리즘
   - 모든 간선의 플로를 0으로 둔 상태에서 시작해서 소스에서 싱크로 플로를 더 보낼 수 있는 증가 경로가 더 이상 존재하지 않을 때까지 반복적으로 증가 경로를 찾아서 최대 플로 값을 구하는 방법
   - 순방향 간선 ↔ 역방향 간선
   - 잔여 용량 → 순방향 간선의 경우 해당 간선에 대해서 플로를 실제로 증가시킬 수 있는 값을 의미하고, 역방향 간선의 경우에는 간선에 부여된 플로를 줄일 수 있는 값을 의미
   - 증가 경로의 여유량 → 경로에 포함된 모든 간선의 잔여 용량 중 가장 작은 값 → 해당 경로를 사용해서 증가시킬 수 있는 플로 값
   - 성능 → O(|E|F)
   - 간선의 용량이 무리수이면 알고리즘이 종료하지 않을 수 있음
   - 증가 경로를 선택할 때 깊이 우선 탐색 사용 → 에드몬즈-카프 알고리즘은 너비 우선 탐색 적용
   - 커트 → 소스와 싱크가 각각 서로 다른 집합에 속하도록 정점 집합을 두 개의 집합으로 나누었을 때 두 집합을 연결하는 간선의 집합