최단 경로 알고리즘 선택과 음의 가중치 처리
Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson 알고리즘의 조건과 복잡도를 비교하고 음의 가중치·음의 사이클 처리 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
최단 거리는 알고리즘보다 입력 조건에서 갈린다
그래프 최단 경로 문제는 경로 비용을 간선 가중치의 합으로 정의한다. 그러나 단일 출발점 최단 경로(SSSP), 단일 쌍 최단 경로(SPSP), 모든 쌍 최단 경로(APSP) 중 무엇을 구하는지와 음의 가중치 허용 여부에 따라 사용할 수 있는 알고리즘이 달라진다.
유향·무향 그래프인지, 가중·비가중 그래프인지도 함께 확인해야 한다. 특히 음의 사이클이 존재하면 해당 사이클에 도달 가능한 일부 정점 쌍에서는 최단 경로가 정의되지 않는다. 거리를 계속 줄일 수 있기 때문이다.
결과는 보통 거리 배열 dist와 전임자 배열 prev로 관리한다. APSP에서는 next 행렬을 두어 경로를 복원할 수 있다. 음의 사이클이 발견될 때는 단순 오류로 끝내지 않고, 이를 보고하고 사이클 경로를 반환하는 절차가 필요하다.
입력 단계에서는 그래프 G(V,E), 가중치 w(e), 그리고 SSSP·APSP 요구를 확정한다. 이후 음의 가중치와 음의 사이클을 검증하고, 그래프 구조에 맞는 알고리즘을 실행한다. 출력에는 최단 거리와 경로 복원 정보, 예외 상황의 음의 사이클 보고가 포함된다.
비음수 비용 그래프에서는 Dijkstra가 빠르게 확정된다
Dijkstra 알고리즘은 우선순위 큐(힙)에서 가장 가까운 정점을 꺼내며 거리를 확정한다. 확정된 정점의 거리는 이후 변하지 않는다는 성질을 이용한다.
바이너리 힙을 사용할 때 시간복잡도는 O((V+E) log V)이며, 인접 리스트로 표현한 희소 그래프에 적합하다. 다만 모든 간선 가중치가 비음수여야 한다. 음의 가중치가 섞이면 결과가 잘못될 수 있으므로 실행 전 데이터 검증 또는 전처리가 필요하다.
음의 가중치를 받아들여야 한다면 Bellman-Ford
Bellman-Ford는 전체 간선을 V-1회 완화(relaxation)한다. 그 뒤에도 추가 완화가 가능하면 음의 사이클이 존재한다고 판단한다.
시간복잡도는 O(VE)다. 중소규모 그래프이거나 음의 가중치를 반드시 다뤄야 하는 환경에 맞는다. 반복 중 거리가 더 이상 변하지 않으면 조기 종료할 수 있으며, 경로 존재 여부와 음의 사이클을 함께 다룰 수 있다는 점이 운영상 강점이다.
모든 정점 쌍의 거리를 한 번에 계산하는 방식
Floyd-Warshall은 중간 정점 k를 차례대로 허용하며 거리를 갱신하는 행렬 기반 동적 계획법이다. next 행렬을 함께 관리하면 실제 경로도 복원할 수 있다.
시간복잡도는 O(V^3), 메모리 사용량은 O(V^2)다. 밀집 그래프나 정점 수가 수천 이하인 경우에 적합하다. 음의 가중치를 허용하며, diag(dist)[i][i] < 0이면 음의 사이클을 탐지할 수 있다.
Johnson 알고리즘은 음의 간선이 있는 희소 그래프의 APSP에 맞춘다. Bellman-Ford로 잠재치(potential) h(v)를 구한 뒤 간선을 재가중치화하고, 비음수화된 그래프에서 각 정점을 출발점으로 Dijkstra를 수행한다.
복잡도는 O(VE + V E log V) ≈ O(VE log V)다. 음의 사이클이 없어야 하며, 재가중치 계산 후 원래 거리로 되돌리는 단계가 필요하다.
알고리즘별 제약과 운영 특성
| 알고리즘 | 성능(시간복잡도) | 메모리 | 음의 가중치 | 음의 사이클 검출 | 확장성(희소/밀집) | 운영 편의 |
|---|---|---|---|---|---|---|
| Dijkstra | O((V+E) log V) | O(V+E) | 불가 | 불가 | 희소 우수 | 구현 용이, 빠른 응답 |
| Bellman-Ford | O(VE) | O(V) | 가능 | 가능 | 중소규모 적합 | 예외 처리 명확 |
| Floyd-Warshall | O(V^3) | O(V^2) | 가능 | 가능 | 소~중간 V, 밀집 적합 | APSP 일괄 계산 |
| Johnson | O(VE log V) | O(V+E) | 가능(재가중치) | BF 단계에서 가능 | 대규모 희소 적합 | 구현 복합, 범용성 우수 |
라우팅부터 위험 분석까지의 적용 범위
OSPF는 링크 상태 기반으로 Dijkstra를 적용하며 비음수 비용을 전제로 한다. RIP는 거리 벡터 기반으로 Bellman-Ford 원리를 적용하므로, 수렴 지연과 루핑을 막는 기법이 필요하다.
금융·거래 아비트리지 탐지에서는 로그 변환 후 음의 가중치 그래프로 모델링하고, 음의 사이클 탐지로 무위험 이익 기회를 식별할 수 있다. 물류나 지도 경로안내에서는 정적 비용에 Dijkstra 또는 반복 Dijkstra를 적용하고, 동적 가중치가 바뀔 때는 부분 재계산을 고려한다. 허브-스포크 네트워크에서 APSP가 필요하면 Floyd-Warshall 또는 Johnson을 선택한다.
보안·위험 분석에서는 비용을 리스크로 모델링해 임계 비용 이하 경로를 찾고, 음의 사이클을 리스크 누적 오류로 검증할 수 있다.
운영에 넣기 전 확인할 항목
문제 스펙에서 SSSP·APSP, 정점과 간선의 규모, 가중치의 부호와 타입(정수·실수)을 먼저 정의한다. 이어 음의 간선과 사이클을 확인한다. 무향 그래프의 음수 간선은 양방향 음수로 인해 즉시 음의 사이클이 될 수 있으므로 별도 검토가 필요하다.
그래프의 희소·밀집 특성과 응답 지연 요구를 반영해 알고리즘을 고른다. 경로 복원을 위해 prev 또는 next 행렬을 어떤 범위까지 저장할지도 정해야 한다. 이는 메모리와 성능의 트레이드오프다.
도달 불가 노드는 무한대로 처리하고, 음의 사이클은 명시적으로 보고해야 한다. 숫자 오버플로와 부동소수 정밀도도 점검 대상이다.
대규모 희소 그래프에서 Johnson을 적용하면 APSP 계산 시간을 10배 이상 단축 가능 사례가 있으며, Dijkstra의 힙 최적화로 SSSP 평균 지연을 ms 단위로 달성할 수 있다. 음의 사이클 검출은 잘못된 비용 모델링을 조기에 찾게 하고, 일관된 경로 복원 정보는 디버깅과 감사 가능성을 높인다. 선택 플로우와 도달 불가·사이클 장애 시나리오를 표준화하면 운영자 의사결정 시간을 줄이고 오류 전파를 최소화할 수 있다.
갱신 빈도와 표현 방식도 결과에 영향을 준다
실수 가중치는 부동소수 오차가 누적될 수 있으므로 EPS 기반 비교와 정규화·스케일링을 적용한다. 간선 갱신이 빈번하면 다이나믹 SSSP, 예를 들어 유지보수형 다익스트라나 부분 재계산 전략을 검토한다.
Floyd-Warshall은 루프 병렬화가 쉬우며 GPU 가속 시 V^3 연산의 효율을 개선할 수 있다. 희소 그래프는 인접 리스트와 바이너리·피보나치 힙을, 밀집 그래프는 인접 행렬을 사용한다. 테스트 스위트에는 랜덤 그래프와 단절 그래프, 동일 비용 다중 경로, 음의 간선이 섞인 경계 사례를 포함한다.