All
벨만-포드 알고리즘 (Bellman-Ford)
•
하나의 출발점에서 나머지 모든 정점까지 최단 경로를 찾는 알고리즘
•
데이크스트라 알고리즘은 음의 가중치를 가진 간선이 있으면 사용할 수 없지만, 벨만-포드는 음의 가중치가 있더라도 최단 경로를 찾을 수 있다
•
음의 사이클(전체 경로의 가중치 합이 음수인 순환)이 존재하면 최단 경로가 정의될 수 없으므로 사용할 수 없음
동작 방식
•
그래프의 모든 간선들을 확인하며, 출발점으로부터 각 정점까지의 최소 거리를 반복적으로 갱신
•
정점의 수(|V|)가 n개라면, 최대 (n-1)번 동안 전체 간선을 확인하여 최소 거리를 업데이트
•
매 반복마다 아래 식으로 거리 값을 갱신
◦
여기서 d\[v\]는 출발점에서 정점 v까지의 현재 최단 거리
◦
w(u, v)는 정점 u에서 v로 가는 간선의 가중치
•
d\[v\] = min(d\[v\], d\[u\] + w(u, v))
•
음의 사이클이 존재하는지 판별하는 방법:
◦
(n-1)번 반복 이후, 한번 더 간선을 점검하여 거리가 또 줄어들면 음의 사이클이 존재하는 것으로 판단
특징과 성능
•
음의 가중치 간선 처리가 가능하지만, 음의 사이클은 처리 불가능
•
실제로는 이전 단계에서 갱신된 거리 값만 다음 단계에 이용하면 더 효율적으로 수행 가능
•
최악의 경우 시간 복잡도: O(|V|×|E|) (정점 수 × 간선 수)
플로이드 알고리즘 (Floyd-Warshall)
•
모든 정점 쌍 간의 최단 경로(All-Pairs Shortest Path)를 구하는 알고리즘
•
음의 가중치 간선은 허용되지만, 음의 사이클은 허용되지 않음
•
동적 프로그래밍(dynamic programming) 방법을 사용하여 최적의 경로를 찾음
동작 방식
•
초기 단계에서는 정점을 하나도 경유하지 않는 직접 연결된 간선의 거리로 초기화
•
이후 경유할 수 있는 정점을 하나씩 늘려가며 모든 정점 쌍 간의 최소 거리를 갱신
•
갱신 규칙:
◦
D[i][j]: 정점 i에서 j까지의 현재 알려진 최단 거리
◦
k: 중간에 경유하는 정점 번호
•
•
이 과정을 모든 정점 k에 대해서 반복하면, 최종적으로 모든 정점 쌍 간의 최단 거리를 얻을 수 있음
•
최단 경로 자체를 찾기 위해 별도의 배열 P\[i\]\[j\]를 사용하여 경로를 추적할 수도 있음
특징과 성능
•
모든 정점 쌍 간의 최단 경로를 한 번에 계산
•
구현이 간단하고 이해가 쉬운 편이나 정점 수가 많아지면 계산 시간이 급증
•
시간 복잡도: O(|V|³) (정점 수의 세제곱)
포드-풀커슨 알고리즘 (Ford-Fulkerson)
•
네트워크에서 한 지점(소스, source)에서 다른 지점(싱크, sink)까지 흘릴 수 있는 최대 유량(Maximum Flow)을 찾는 알고리즘
•
유량(Flow): 한 노드에서 다른 노드로 보낼 수 있는 데이터(또는 흐름)의 양
•
네트워크(Network): 정점과 간선으로 구성된 유향 그래프에서 간선마다 데이터 용량(capacity)이 정의된 구조
기본 개념
•
플로(Flow): 간선(u,v)을 통해 흐르는 현재 흐름 양. 초기에는 0
•
용량(Capacity): 각 간선이 처리할 수 있는 최대 흐름
•
증가 경로(Augmenting path): 소스에서 싱크까지 흐름을 추가로 보낼 수 있는 여유가 있는 경로
•
잔여 용량(Residual Capacity): 간선이 추가로 흘릴 수 있는 여유량
•
역방향 간선(Backward edge): 이미 흘러간 플로를 되돌릴 수 있게 함 (유량 조정)
동작 방식
1.
모든 간선의 초기 플로를 0으로 설정
2.
소스에서 싱크까지 증가 경로를 찾는다(DFS나 BFS 이용)
3.
증가 경로에서 추가로 보낼 수 있는 여유량을 찾고(경로상의 최소 잔여 용량), 이를 이용해 플로를 증가킴
4.
이 과정을 더 이상 증가 경로가 없을 때까지 반복
5.
증가 경로가 없으면 종료되며, 이때의 플로 합이 최대 유량이 됨
추가 개념
•
에드몬즈-카프 알고리즘(Edmonds-Karp): 포드-풀커슨의 BFS 버전으로, 항상 최단 길이의 증가 경로를 찾아 더 빠르게 종료됨을 보장
•
커트(cut): 소스와 싱크를 분리할 때 간선의 집합을 의미하며, 최소 커트 용량은 항상 최대 유량과 같습니다(최대 흐름-최소 컷 정리).
특징과 성능
•
간선의 용량이 무리수일 경우 알고리즘 종료가 보장되지 않을 수 있음
•
증가 경로 선택 전략에 따라 성능 차이가 크게 발생할 수 있음
•
최악의 시간 복잡도: O(|E|×F) (F는 최대 유량 값, |E|는 간선의 수)