네트워크 최적화를 위한 SPT·Minimum Cut·Steiner Tree 선택
Shortest Path Tree, Minimum Cut, Steiner Tree의 문제 조건과 알고리즘 선택 기준을 네트워크 설계·운영 관점에서 정리한다.
2026-08-14 · 최초 발행 2024-04-29
경로, 병목, 배선 비용은 서로 다른 그래프 문제다
네트워크 설계와 운영에서는 최단 경로를 산출해야 할 때도 있고, 트래픽을 가르는 취약 구간을 찾아야 할 때도 있다. 여러 수요 지점을 잇는 배선 비용을 줄이는 일이 본체인 경우도 있다. Shortest Path Tree, Minimum Cut, Steiner Tree는 각각 이 세 요구에 대응하는 대표적인 그래프 최적화 문제다.
모델을 만들 때는 그래프가 방향성을 갖는지, 가중치와 용량이 무엇을 뜻하는지, 음수 가중치를 허용하는지부터 분명히 해야 한다. 지연·대역폭·신뢰도 같은 서비스 수준과 금지 링크·구역 분리 같은 정책 제약도 그래프 모델에 반영할 대상이다.
단일 소스의 경로를 묶는 Shortest Path Tree
Shortest Path Tree(SPT)는 한 소스에서 모든 노드까지 가는 최단 경로를 트리로 구성한다. 각 노드에 이르는 경로 길이 합이 최소가 되는 구조다.
비음수 가중치 그래프에는 Dijkstra 알고리즘을 적용한다. 음수 가중치가 있다면 Bellman-Ford를 사용해야 하며, 음수 사이클이 존재하면 최단 경로 자체를 정의할 수 없다. 가중치가 없는 그래프라면 BFS가 선택 대상이다.
우선순위 큐 기반 Dijkstra의 시간 복잡도는 O(m log n)이고, Bellman-Ford는 O(nm)이다. 엣지 비용이 바뀌는 환경에서는 전체 계산을 반복하기보다 부분 재계산 전략을 마련하는 편이 운영에 맞다. 다중 소스 SPT는 병렬 처리나 영역화로 확장할 수 있다.
분리 비용을 드러내는 Minimum Cut
Minimum Cut은 그래프를 두 부분으로 나눌 때 잘린 간선의 용량 합이 가장 작아지는 분할을 찾는다. s-t 최소 컷은 소스 s와 싱크 t를 분리하는 최소 용량 컷이다.
Max-Flow Min-Cut 정리에 따라 최대 유량 값과 최소 컷 값은 동치다. 따라서 Dinic이나 Push-Relabel 같은 최대 유량 알고리즘으로 계산할 수 있다. Dinic의 일반적인 최악 복잡도는 O(mn), Push-Relabel은 O(n^3)이며, 실무에서는 수십만 간선까지 안정 동작한다.
컷셋에 포함된 간선의 포화 상태, 즉 Residual 0을 확인하면 병목의 원인을 진단하는 데 도움이 된다. 배치형 최대 유량 처리나 샤딩·영역화도 규모가 커질 때 고려할 수 있다.
단자를 연결하는 Steiner Tree
Steiner Tree는 지정된 단자 집합 T를 모두 연결하는 최소 비용 부분그래프를 찾는 문제다. 단자에 속하지 않는 스테이너 노드를 추가할 수 있다는 점이 MST와 다르다.
이 문제는 NP-난해다. 그래프나 메트릭 환경에서는 KMB 등의 2-근사 또는 개선된 근사 알고리즘과 휴리스틱을 사용한다. 터미널 수가 적을수록 근사 품질이 좋아지는 경향이 있으며, 근사 비율과 실행 시간의 균형이 선택 기준이 된다. KMB는 메트릭 폐포 계산과 SPT 반복을 통해 실무 시간 내 처리할 수 있다.
정책 제약이 더해지면 라그랑주 이완이나 벌점 기법으로 실용적인 해를 유도할 수 있다. 터미널 전처리 과정에서 겹치는 노드와 명백한 잎을 제거하는 방식도 성능 개선에 활용된다.
운영 환경에서의 적용 지점
SDN과 라우팅 최적화에서는 링크 지연·손실 가중치와 정책 제약을 입력으로 두고 SPT를 계산할 수 있다. 산출된 경로 트리에 ECMP나 정책 라우팅을 결합하면 장비별 포워딩 엔트리와 경로 지연 보증으로 이어진다.
링크 용량, 임계 트래픽 패턴, 중요 노드 집합이 주어졌다면 s-t Minimum Cut 분석으로 병목 구간을 식별할 수 있다. 이 결과는 증설 우선순위와 장애 시 서비스 분리 시나리오를 설계하는 기준이 된다.
광·케이블 인프라와 멀티캐스트는 설치 비용 지도와 수요 지점 집합을 바탕으로 Steiner Tree 근사를 적용할 수 있다. 지리 제약을 반영한 설치 경로, 예상 CAPEX, 단계별 롤아웃 계획이 결과물이다.
데이터센터 L2/L3 오버레이에서는 랙 간 비용·대역폭 및 브로드캐스트 도메인 정책을 입력으로 삼는다. SPT 기반 멀티캐스트 트리와 Minimum Cut 기반 장애 도메인 분리를 함께 사용해 그룹별 트리와 장애 시 페일오버 플랜을 구성할 수 있다.
목적에 맞춰 계산하고 정책을 검증하는 흐름
알고리즘 특성과 운영상 차이
| 항목 | Shortest Path Tree | Minimum Cut | Steiner Tree |
|---|---|---|---|
| 목적 | 단일 소스→전 노드 최단 경로 트리 | s,t 분리 최소 용량 컷 | 단자 집합 연결 최소 비용 부분그래프 |
| 대표 알고리즘 | Dijkstra, Bellman-Ford | Dinic, Push-Relabel | KMB 2-근사, 메트릭 폐포 기반 |
| 전형적 시간 복잡도 | O(m log n) / O(nm) | O(mn) 또는 O(n^3) 최악 | 근사: 다중 SPT + MST 수준 |
| 확장성 | 고확장성, 스트리밍 가능 | 중~고, 그래프 밀도 영향 | 중, 터미널 수 의존 |
| 일관성/최적성 | 정확 최적해 | 정확 최적해 | 근사 보장(예: 2-근사) |
| 운영 편의 | 높음, 디버깅 용이 | 중간, 파라미터·잔여망 관리 필요 | 중간, 터미널·제약 설계 필요 |
SPT와 Minimum Cut은 전제가 충족되면 정확한 최적해를 보장한다. 반면 Steiner Tree는 품질과 계산 시간의 절충이 필요하다. 어느 기법이든 계산 결과를 SLA와 정책 제약에 다시 대조하는 단계가 빠지면 운영에서 그대로 쓰기 어렵다.
NetworkX 활용 예시
전제조건은 다음과 같다.
- Python 3.10+
- networkx ≥ 3.2
- 설치: pip install networkx
# 환경: Python 3.10+, networkx 3.2+
import networkx as nx
from networkx.algorithms.approximation import steiner_tree
# 1) Shortest Path Tree (SPT)
G = nx.Graph()
G.add_edge('A', 'B', w=2)
G.add_edge('B', 'C', w=1)
G.add_edge('A', 'C', w=5)
G.add_edge('C', 'D', w=2)
G.add_edge('B', 'D', w=4)
def has_negative_weight(graph, weight='w'):
return any(data.get(weight, 0) < 0 for _, _, data in graph.edges(data=True))
source = 'A'
if has_negative_weight(G, 'w'):
dist, paths = nx.single_source_bellman_ford(G, source, weight='w')
else:
dist, paths = nx.single_source_dijkstra(G, source, weight='w')
print('SPT dist:', dist) # 각 노드까지의 최단 거리
print('SPT path to D:', paths['D'])
# 2) Minimum Cut (s-t)
D = nx.DiGraph()
D.add_edge('s', 'u', cap=3)
D.add_edge('s', 'v', cap=2)
D.add_edge('u', 'v', cap=1)
D.add_edge('u', 't', cap=2)
D.add_edge('v', 't', cap=3)
cut_value, (S, T) = nx.minimum_cut(D, 's', 't', capacity='cap')
print('Min-Cut value:', cut_value)
print('Partition S:', S, 'T:', T)
# 3) Steiner Tree (근사)
terminals = {'A', 'D'}
ST = steiner_tree(G, terminals, weight='w') # 무방향 그래프 권장
print('Steiner edges:', list(ST.edges(data=True)))Dijkstra는 음수 가중치에서 부정확하므로 음수 사이클 탐지가 필요하다. Minimum Cut은 컷셋 엣지의 포화를 확인해 병목을 해석한다. Steiner Tree는 터미널 전처리로 계산 효율을 높일 수 있다.
비용과 성능을 함께 보는 운영 효과
Steiner 기반 배선·케이블 설계는 MST 대비 총 길이를 1030% 절감할 수 있다. Minimum Cut 분석을 바탕으로 목표를 둔 증설은 CAPEX 우선순위를 1525% 효율화할 수 있다.
SPT 기반 지연 최소 라우팅은 P95 지연을 10~20% 개선할 수 있다. 컷 값을 높이도록 리던던시를 추가하면 단일 장애 상황의 서비스 가용성을 개선할 수 있다.
자동화 파이프라인을 도입하면 변경 배포 리드타임을 30% 이상 단축할 수 있다. 대규모 그래프에서는 증분 재계산을 통해 실시간성을 유지한다.