[알고리즘] 10강 - 그래프(3)

✅ 1. 벨만-포드 알고리즘

(1) 벨만-포드 알고리즘이란?

• 벨만-포드 알고리즘: 데이크스트라 알고리즘과 동일하게 단일 출발점으로 부터 모든 정점간의 최단 경로를 구하는 알고리즘임.
• 단, 데이크스트라 알고리즘은 음의 가중치를 갖는 간선이 존재하는 경우에는 처리가 불가능 했지만, 벨만-포드 알고리즘은 음의 가중치를 갖는 간선이 존재하는 경우에도 처리가 가능한 알고리즘임.
• 대신 조건은 음의 사이클이 없는 경우에 한해서 가능함.
• 즉, 데이크스트라 알고리즘의 경우 가장 짧은 간선 하나를 기준으로 그 끝에 있는 정점을 선택하며 퍼져나가는데 반해, 벨만-포드 알고리즘은 그래프에 존재하는 모든 간선을 매 라운드마다 훑으며 최단 거리를 업데이트하기 때문에 음수 가중치를 발견하더라도 다음 라운드에서 반드시 그 값을 반영하게 되는 원리임.
• 즉, 벨만 포드는 모든 경로의 경우의 수를 하나도 빠짐없이 검증하는 알고리즘으로 볼 수 있음.

(2) 벨만-포드 알고리즘 - 수행 과정

(3) 벨만-포드 알고리즘 - 로직

• (1) 초기화: 모든 정점에 대해서 초기화 반복문을 수행함.
• (2) 간선 완화 반복: 정점의 개수가 V개일 때, 총 V-1번 반복하며, 매 반복마다 그래프에 있는 모든 간선(E개) 하나하나 확인하며, 이 과정을 거치면 모든 정점까지의 최단 거리가 수학적으로 확정됨.

(4) 벨만-포드 알고리즘 - 예시(1)

• 정점(1) 의 부수된 간선의 정점(2, 3)의 최단 경로는 2(4), 3(2)가 되고, 1 -> 2 -> 4의 경우에는 정점(3)과 정점(4)는 각 2, 3의 가중치를 가지게 되어 최종적으로 최단 경로(4+2+3= 9)의 최단 경로를 얻을 수 있지만, 1 -> 2 -> 3 -> 4 의 경우에는 정점(3)과 정점(4)는 각 1, 2의 가중치를 가지기 때문에 최종적으로 4+1+2= 7의 최단 경로를 얻을 수 있음.
• 결과적으로 4+1+2 = 7 의 최단 경로가 더 짧기 때문에 해당 경로를 선택하는 원리임.
• 즉, 데이크스트라 알고리즘의 음수가 있을 경우에는 최단 경로를 구할 때 하나의 경로에서 각 경로마다 최적해를 구하면서 나아가는데 문제는 음수가 들어가게 되면, 최적해가 안나올 수 있다는 문제가 있기 때문에 벨만-포드는 단순하지만 강력하게 모든 정점의 경로에 해당하는 경우의 수를 파악하는 원리임. (DP 방식을 활용함) 동적 프로그래밍 방법
• 쉽게 말해, 출발 정점의 부수된 간선의 가중치의 최단 경로를 구하고, 부수된 정점들의 또 부수된 모든 간선들의 최단 경로를 구해보고 그 중에서 최적해를 구하고, 또 그 정점들의 부수된 간선의 최단 경로를 구해 최적해를 구해나가는 방식임.

(5) 벨만-포드 알고리즘 - 예시(2)

• 벨만-포드 알고리즘의 경우 출발 정점으로부터 간선 몇개를 사용하느냐에 따라서 경우의 수가 갈리며, 몇 개의 다리를 건너야 할지 미리 알 수 없기 때문에 순차적으로 간선을 늘리며 최단 경로를 구하는 방식임.

(6) 벨만-포드 알고리즘 - 성능과 특징

• 시간 복잡도 O(V * E): V - 1번의 루프(정점 수에 비례) 안에서 매번 모든 간선(E개)을 전수 조사하기 때문에 해당 시간 복잡도를 가질 수 있음. 즉, 벨만-포드는 모든 간선을 무식하게 다 훑는 과정 때문에 다익스트라보단 훨씬 느림.

• 음의 가중치를 갖는 간선이 있는 경우에는 데이크스트라 알고리즘 적용이 불가능하기 때문에, 벨만-포드 알고리즘을 적용 할 수 있지만, 음의 가중치를 갖는 간선이 없는 경우에는 성능면에서 데이크스트라 알고리즘이 뛰어나기 때문에 데이크스트라 알고리즘을 쓰는게 효율적임.

---

✅ 2. 플로이드 알고리즘

(1) 플로이드 알고리즘이란?

• 플로이드 알고리즘: 모든 쌍의 최단 경로를 구하는 알고리즘이다. ( 정확한 명칭은 플로이드 워셜 알고리즘임 )
• 쉽게 말해, 임의의 정점 두개가 한 쌍이 되며, 해당 정점간의 최단 경로를 구하는 알고리즘으로 볼 수 있음.
• 즉, 데이크스트라, 벨만 포드의 경우 단일 출발점으로부터 모든 정점간의 최단 경로였다면, 플로이드는 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 방식이며, 결과적으로 플로이드 알고리즘은 데이크스트라와 벨만포드가 구하는 출발점에서 모든정점의 최단 경로 또한 포함한다고 볼 수 있음. ( 확장판으로 보면 됨. )
• 조건: 경로의 길이가 음인 사이클이 존재하지 않아야 적용이 가능한 알고리즘임.
• 적용 기법: 동적 프로그래밍 방법이 적용된 알고리즘임.

(2) 플로이드 알고리즘 - 인접 행렬 표현

• 플로이드 알고리즘은 기본적으로 인접 행렬을 기반으로 동작하며, 그 결과물 또한 2차원 행렬 형태로 나타난다.
• D^(k): D(인접 행렬)를 통해 k 단계별로 k 이하인 정점만을 경유하는 정점 i에서 j까지 최단 경로를 천천히 구하면서 k 의 단계를 늘려가며, 각 단계마다 점화식을 통해서 더 짧은 거리를 구한 뒤 갱신을 해주는 것임.
• 점화식: 이전 값으로 현재 값을 정의하는 모든 공식을 의미한다. ( 피보나치 수열, 등비/등차 수열 등 이런 이전 값을 통해 현재 값을 정의하는 모든 공식들을 포괄하는 용어임 )

• 알고리즘 점화식: 재귀 호출 구조에서 사용하는 식을 의미하며, 수학적 점화식과 구조가 동일하며, 이전 값으로 현재 값 정의와 동일하게 이전 호출로 현재 호출을 정의하는 같은 본질을 가지고 있음.
• 즉, 수학적 점화식이라는 큰 틀 안에서, T(n)에 "시간"이라는 의미를 부여한 것이 알고리즘 점화식임.

(3) 플로이드 알고리즘 - 예시(1)

초기화 과정: 모든 정점간의 연결을 인접행렬로 표현 및 초기화 진행 D(0): 중간 정점 없이, 직접 연결된 거리만 계산 ( 초기화 )

D(1): 정점 1번을 거쳐도 된다고 허용 및 해당 정점 1번을 경유 했을 때 더 짧아지는 경로가 있는지 체크 즉, (4,2) , (4,3) 만 정점 1을 거쳐가기 때문에 갱신이 가능함. 최소 값 갱신: 점화식을 활용해서 이전의 값과 비교 후 더 짧은 경로의 값으로 갱신을 해줌.

D(2): 정점 2번을 거쳐도 된다고 허용 및 이전 정점 1번 또한 거쳐도 됨. ( 경유 했을 때 더 짧아지는 경로 체크 )

• D(0) : 중간 정점 없이, 직접 연결된 거리만
• D(1) : 정점 1번을 거쳐도 된다고 허용
• D(2) : 정점 1, 2번을 거쳐도 된다고 허용
• D(k) : 정점 1~k번을 거쳐도 된다고 허용
• D(|V|) : 모든 정점을 거쳐도 됨 → 최종 최단거리 완성
• 점화식 분석: d(k)ij = min( d(k-1)ij,  d(k-1)ik + d(k-1)kj )
                                                      ↑                ↑
                                                기존 거리      정점 k를 경유하는 경우의 거리

• D(k) 단계에서 k를 점진적으로 늘리며, 해당 정점을 거쳐가도록 허용을 점진적으로 푸는 이유는, 이미 계산된 최단 거리를 재사용하기 위해서 단계를 나누는 것임. 즉, 사실상 경로의 조합이 기하급수적으로 많아져서 계산이 불가능해지기 때문에 효율을 위해서 점진적으로 늘리며, 정점을 거쳐가도 된다고 허용을 시켜주는 것임.

(4) 플로이드 알고리즘 - 예시(2)

• D^(0): 모든 정점을 인접 행렬로 만드는 초기화 과정
• D^(1): 1번 정점을 거치는 경우인 (4,2) , (4,3) 에 대한 거리값을 갱신

(5) 플로이드 알고리즘 - 성능과 특징

• 플로이드 알고리즘 시간 복잡도: O(n^3)

• 플로이드 알고리즘은 동적 프로그래밍 방법을 적용한 알고리즘임.
• 동적 프로그래밍 방법: 한 번 구한 답은 다시 구하지 않는다는 전략이며, 복잡하고 큰 문제를 한 번에 풀려고 하면 너무 어렵기 때문에, 이를 작은 하위 문제로 나눈 뒤, 그 결과를 저장해 두었다가 나중에 더 큰 문제를 풀 때 가져다 쓰는 방식임.
• 플로이드 알고리즘 동적 프로그래밍 방법인 이유: 큰 문제(1번부터 n번까지의 모든 정점간의 최단 거리 구하기)를 작은 문제(1번부터 k번까지만 경유지로 사용해서 최단 거리 구하기)를 통해서 해결하는 원리임.
• 데이크스트라 알고리즘으로 모든 쌍 최단 경로 구하기: 데이크스트라 알고리즘은 한 정점에서 모든 정점간의 최단 경로를 구하는 알고리즘인데, 모든 정점에 대한 최단 경로를 구하게 되면 결국 데이크스트라 알고리즘으로도 구할 수 있음 => O(V^3)
• 하지만, 플로이드 알고리즘이 모든 쌍을 구하는데 있어서 더 간단하기 때문에 더 빠르게 구할 수 있음. 

---

✅ 3. 포드-풀커슨 알고리즘

(1) 네트워크 플로 문제란?

• 네트워크 플로 문제란?: “흐를 수 있는 양(flow)을 제한된 경로를 통해 어떻게 보내야 하는가”를 다루는 그래프 문제임.
• 네트워크 N: 네트워크 구성 요소로는 방향 그래프 G(V,E), s(시작점), t(도착점), c(간선의 용량) 으로 구성되어있음.
• 즉, 네트워크 플로 문제는 방향 그래프에서 각 간선(edge)에 용량(capacity)이 주어질 때, 시작점(source)에서 도착점(sink)까지 흐름(flow)을 제약 조건을 만족하며 보내는 문제로 보면 됨.
• 예를들면, 수도관, 네트워크, 인터넷 패킷 전송, 물류 배송 교통 흐름, 송전망 등을 그래프화 해서 네트워크 플로 문제를 대입해서 해결 할 수 있는 느낌임.
• 최대 유량 문제: 네트워크 플로 문제의 가장 대표적인 형태 중 하나로, 최대 유량 문제는 전체 네트워크에서 시작(Source)부터 도착점(Sink)까지 보낼 수 있는 흐름의 최대량을 구하는 문제임.
• 포드-풀커슨 알고리즘이 네트워크 플로의 최대 유량 문제에 대한 알고리즘임.
• 정리: 네트워크 플로는 흐름이 존재하는 네트워크 문제 전체를 다루는 큰 개념이고, 그 안에 최대 유량 문제 같은 세부 문제가 존재한다. 그리고 포드-풀커슨은 최대 유량 문제를 해결하는 대표 알고리즘이다.
• 또한, 단일 소스 - 단일 싱크 문제로, 모든 정점 쌍에 대한 유량을 한 번에 구하는 것이 아님. 단일 정점 쌍에 대한 유량임.

(2) 포드-풀커슨 알고리즘이란?

• 포드-풀커슨 알고리즘: 네트워크 플로 문제에서 최대 유량 문제에 대한 최초로 제시된 가장 기초적인 해결 방법의 알고리즘이며, 가장 기초적인 방법이기에 단순히 플로 값을 증가시킬 수 있는 모든 경우의 수를 탐색해서 적용을 하는 방식임.
• 단점: 종료가 보장되지 않기 때문에, 에드몬즈-카프 알고리즘으로 발전이 됨.
• 원리: 모든 간선의 플로를 0으로 둔 상태에서 시작, 증가 경로가 더 이상 존재하지 않을 때까지 반복적으로 경로를 찾아서 최대 플로 값을 구하는 원리임.

• 증가 경로: 소스(출발 정점)에서 싱크(도착 정점)까지 더 많은 플로를 보낼 수 있는 경로를 의미한다.
• 역방향 간선의 존재 이유: 해당 경로 말고 다른 경로로 보내는게 더 효율적이라고 판단이 되면, 이미 보낸 흐름을 취소 할 수 있도록 하기 위해서 역방향 간선이 존재하는 것임.

• 잔여 용량: 간선에서 추가로 플로를 증가시킬 수 있는 여유 용량을 의미한다.
• 쉽게 말해, a - b 간선의 용량이 10인데 5만큼 사용 중이라면, 잔여 용량은 5이다. ( 5만큼 남아있기 때문에 )

• 증가 경로의 여유량: 경로에 포함된 모든 간선의 잔여 용량 중 최소값을 의미하며, 이는 곧 해당 경로를 사용해서 증가시킬 수 있는 플로 값으로 볼 수 있음.

S -> A -> B -> T
S ──10──> A ──3──> B ──7──> T
- 잔여 용량: S -> A = 10, A -> B = 3, B -> T = 7
- 흐름이 결국 최소값인 A -(3)> B 간선에 의해서 제한됨.

• 쉽게 말해, 위 예시와 같이 경로의 흐름이 잔여 용량 중 최소값인 간선에 의해서 제한되기 때문에 결국 증가 경로에서 가장 좁은 간선이, 그 경로로 추가 가능한 최대 유량으로 볼 수 있음.

(3) 포드-풀커슨 알고리즘 - 과정

(4) 포드-풀커슨 알고리즘 - 예시(1)

초기화: 간선의 플로와 간선의 용량의 초기화를 진행함. 간선의 용량: 각 간선이 버틸 수 있는 최대 수치로 설정이 됨. 간선의 플로: 모든 간선의 현재 유량을 0으로 초기화하는데, 처음에는 아무것도 흐르지 않는 상태임을 나타냄.

증가 경로 s-3-2-t: 증가 경로 상에서 증가 경로 여유량의 간선(용량: 4)을 기준으로 증가 경로상의 모든 간선의 플로가 증가함 (4씩) 증가 경로 여유량: 증가 경로 상의 간선의 용량 - 간선의 용량이며, 간선의 용량을 다 못채운 값을 의미함. 잔여 용량: 증가 경로의 여유량이 곧 해당 간선의 증가 경로상의 여유량으로 볼 수 있음.

증가 경로 s-1-4-t: 증가 경로의 여유량의 간선(용량: 3)을 기준으로 증가 경로상의 모든 간선의 플로가 증가함 (3씩)

증가 경로 s-3-4-t: 증가 경로의 간선의 플로값이 올라간 상태이므로, 최대 용량을 할당 할 수 있는 부분인 s -> 3의 증가 용량 4 + 2 = 6 즉, 2만큼의 잔여 용량에 따라서 증가 경로의 모든 간선의 플로값들이 증가하게됨.

증가 경로 s-1-2-3-4-t: 증가 경로에서 4 -> t 의 간선의 플로값이 5/7 이었으며, 증가 경로의 여유량(잔여 용량)이 제일 작기 때문에 모든 증가 경로상의 간선의 플로값들을 +2 씩 증가 시키게 됨. 역방향 간선: 2 -> 3 부분은 역방향 간선이기 때문에, 2를 증가하는게 아닌 2만큼 간선의 플로값을 빼게 됨.

최대 플로: 소스(시작점) 에서 나가는 플로들의 합(6 + 6 = 12) 12가 최대 플로가 됨. 또한, 싱크(도착점) 으로 들어오는 플로들의 합(5 + 7 = 12) 12가 최대 플로가 됨.

• 최대 플로: 최대 유량으로도 부르며, 가중치가 있는 방향 그래프(네트워크)에서 소스(시작점)로부터 싱크(도착점)까지 동시에 보낼 수 있는 데이터나 자원의 최대 양을 의미함.
• 최대 플로 구하기: 소스(시작점) 에서 나가는 플로들의 합 또는 싱크(도착점)으로 들어오는 플로들의 합 이 두가지 경우 모두 최대 플로의 값으로 볼 수 있음. ( 즉, 소스에서 나가는 플로들의 합과 싱크로 들어오는 플로들의 합은 같음. )
• 최대 플로에서 의미하는 소스에서 나가거나 싱크로 들어오는 플로들은 인접한 정점 즉, 부수된 간선의 가중치 값이 기준임.

(5) 포드-풀커슨 알고리즘 - 예시(2)

• 최대 플로 자체는 동시에 보낼 수 있는 데이터나 자원의 최대 양을 의미하며, 예시(1) 과 동일하게 수행이 됨.

(6) 포드-풀커슨 알고리즘 - 성능과 특징

• 용량으로 무리수를 사용하는 경우: 알고리즘의 종료가 보장되지 못함. ( 즉, 정수로 사용 해야함 )
• 용량 M이 매우 큰 값이면 비효율적임.

• 증가 경로의 선택은 DFS 또는 BFS 적용을 해서 선택함.
• 포드-풀커슨 알고리즘은 기본적으로 DFS를 적용하여 증가 경로 선택을 함.
• 커트(cut): 소스에서 싱크로 가는 모든 길목을 차단하도록 정점들을 두 그룹으로 쪼개는 행위 자체를 의미함.
• 쉽게 말해, 포드 풀커슨 알고리즘 정확성 이런걸 증명하는데 많이 사용되는 개념임.

(7) 정리

• 벨만-포드 알고리즘: 음의 가중치를 갖는 간선이 존재해도 적용할 수 있는 단일 출발점 최단 경로 알고리즘
• 플로이드 알고리즘: 모든 정점 쌍 간의 최단 경로, 동적 프로그래밍 방법
• 포드-풀커슨 알고리즘: 네트워크 플로 문제에서 최대 유량을 구하는 문제