[Algorithm]그래프3

📚벨만-포드 알고리듬

단일 출발점 최단 경로를 구할 수 있는 알고리듬이다. 다익스트라 알고리듬과는 다르게 벨만-포드 알고리듬은 음의 가중치를 갖는 간선이 존재하는 그래프에 대해서도 단일 출발점 최단 경로를 구할 수 있다.(단, 음의 사이클이 없어야 한다.)

📄수행과정

• 초기화: 출발점 s의 거리는 0, 나머지 모든 정점 v들의 거리는 ∞으로 초기화

• 간선을 1 개부터 그래프 간선의 개수 - 1(n - 1)개 까지 사용하는 최단 경로 구함: 모든 간선을 한 번씩 조사하면서 거리값 조정 여부를 결정.

d[v] <- min{기존거리, 간선 <u, v>를 지나는 경우의 거리}: 기존거리와 해당 간선을 지남으로써 결정되는 거리 중 작은 값으로 거리 값을 조정.

실제로 각 단계에서 모든 간선을 조사할 필요 없이 이전 단계에서 거리값이 조정된 정점에 부수된 간선만 조사하여 효율적인 처리 가능.

📄성능과 특징

• 음의 가중치를 갖는 간선이 있는 경우
  • 다익스트라 알고리듬 적용 불가
  • 벨만-포드 알고리듬 적용 가능(음의 사이클 존재하면 적용 불가)
• 음의 가중치를 갖는 간선이 없는 경우
  • 다익스크라 알고리듬 -> O(|V|+|E|)
  • 벨만-포드 알고리듬 -> O(|V||E|)

📚플로이드 알고리듬

모든 쌍 최단 경로 알고리듬(출발점이 정해져 있지 않음. 임의의 두 정점 간 최단 경로 구하는 알고리듬)

• 경로의 길이가 음의 사이클이 존재하지 않는다고 가정

• 동적 프로그래밍 기법 적용

• 경유할 수 있는 정점의 범위가 1인 경로부터 최대 정점 개수(n)인 경로까지 하나씩 정점의 범위를 늘려 모든 정점 간의 최단 경로를 한꺼번에 구함

📄인접 행렬 표현 활용

\[D^{(k)} = (d_{ij}^{(k)})\]

정점 번호가 k 이하인 정점만을 경유하는 정점 i에서 j까지의 최단 경로의 길이

D⁽⁰⁾부터 D⁽ⁿ⁾까지 구해서 최종 결과를 구한다.

D⁽⁰⁾는 정점 i에서 정점 j까지 아무것도 거치지 않는 최단 경로 길이를 의미한다.(그래프를 인접행렬로 표현 -> 초기화)

D⁽⁰⁾부터 D⁽ⁿ⁾까지 구할 때 점화식의 형태로 최종 결과를 구한다.

\[d_{ij}^{(k)} = min(d_{ij}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{kj}^{(k - 1)})\]

기존 거리(정점 i에서 정점 j로 바로 가는 거리)와 정점 k를 경유하는 경우의 거리(i -> k -> j)를 비교하여 작은 값을 선택한다.

📄성능과 특징

• 동적 프로그래밍 방법을 적용한 알고리듬

• 다익스트라 알고리듬으로 모든 쌍 최단 경로를 구할 수 있음
  • 각 정점에 대해 반복적으로 적용 -> O(|V|³)
  • 하지만, 플로이드 알고리듬이 더 간단하므로 빠르게 수행 가능
• P[1..n][1..n]를 활용하면 최단 경로 자체를 구할 수 있음
  • P[i][j] = k(기존 거리보다 정점 k를 경유하는 경우의 거리가 작을 때)

📚포드-풀커슨 알고리듬

📄네트워크 플로 문제

• 주어진 네트워크에 대해 플로(flow)를 최대로 하는 값을 찾는 문제
  • 소스에서 싱크로 보낼 수 있는 플로 값을 최대로 하는 문제 -> 최대 플로 문제
• 네트워크 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}에 대하여 SUM f(u, v) = SUM f(v, w)
  • 소스/싱크를 제외한 모든 정점에 대해 어떤 정점으로 들어오는 양과 나가는 양은 동일
• 플로 값(총 플로) F
  • 소스에서 나가는 플로의 합, 싱크로 들어오는 플로의 합

📄포드-풀커슨 알고리듬

• 최초로 제시된 가장 기초적인 네트워크 플로 해결방법
  • 단순히 플로 값을 증가시킬 수 있는 모든 경우의 수를 탐색해서 적용
  • 종료가 보장되지 않음 -> 에드몬즈-카프 알고리듬으로 발전
• 모든 간선의 플로를 0으로 둔 상태에서 시작해서 증가 경로가 더 이상 존재하지 않을 때 까지 반복적으로 경로를 찾아서 최대 플로 값을 구하는 방법

📝증가 경로

• 소스에서 싱크까지 더 많은 플로를 보낼 수 있는 경로
• 경로상의 간선은 네트워크 N의 간선 방향과 일치하지 않을 수 있음
  • 순방향 간선 -> 간선 <u, v>가 N의 간선과 방향과 같은 경우
  • 역방향 간선 -> 간선 <u, v>가 N의 간선과 방향과 다른 경우
    • <v, u>∈E와 방향이 반대인 간선 -> <u, v>∉E인 가상의 간선
    • c(u, v) = 0, f(u, v) = -f(v, u)
    • 남아 있는 모든 가능한 경로를 더 찾아낼 수 있게 하는 포드-풀커슨 방법의 핵심

📝잔여 용량 r(u, v)

• 간선 <u, v>에서 추가로 플로를 증가시킬 수 있는 여유 용량
  • 순방향 간선 -> r(u, v) = c(u, v) - f(u, v) -> 증가시킬 수 있는 양/값
  • 역방향 간선 -> 원래 간선에 부영된 플로를 줄일 수 있는 양/값

📝증가 경로의 여유량

• 경로에 포함된 모든 간선의 잔여 용량 중 최소값
  • 해당 경로를 사용해서 증가시킬 수 있는 플로 값

📝알고리듬

• 초기화: 간선의 플로/ 간선의 용량(예: 0/8)
• 증가 경로를 찾고 해당 경로의 여유량으로 모든 간선의 플로를 조정하는 과정을 반복

📄성능과 특징

• 시간 복잡도: O(|E| F)
• 간선의 용량에 무리수가 사용되면 알고리듬이 종료하지 않을 수 있다
• 용량이 정수라고 해도 M이 매우 큰 값이라면 비효율적인 결과를 보인다
• 증가 경로 선택은 DFS 또는 BFS 적용
  • 포드-풀커슨 알고리듬 -> 기본적으로 DFS를 적용하여 증가 경로 선택
  • 에드몬즈-카프 알고리듬 -> BFS 적용, O(|V||E|2), 포드-풀커슨 문제 해결
• 커트
  • 소스 s와 싱크 t가 서로 다른 집합에 속하도록 정점의 집합 V를 두 개로 나눈다. 소스는 집합 S에 싱크는 집합 T에 속하게 됨
  • 커트 -> (S; T) ∪ (T; S)
  • (S; T): S의 정점에서 T의 정점으로 향하는 간선의 집합
  • 커트의 용량(플로)은 소스에서 싱크로의 최대 플로와 같다.