벨만-포드 알고리즘 (Bellman-Ford Algorithm)
벨만-포드 알고리즘은 그래프에서 **최단 경로(Shortest Path)**를 구하기 위한 알고리즘으로, 특히 음수 가중치 간선을 포함한 그래프에서도 작동합니다.이 알고리즘은 단순하면서도 강력하며, 음수 사이클(negative weight cycle)을 감지할 수도 있습니다.알고리즘의 특징음수 가중치 허용:다익스트라 알고리즘은 음수 가중치 간선이 있는 그래프에서는 사용할 수 없지만, 벨만-포드 알고리즘은 음수 가중치를 포함한 그래프에서도 작동합니다.음수 사이클 탐지:음수 사이클이 존재하는 경우, 무한히 작은 경로를 만들 수 있기 때문에 최단 경로를 계산할 수 없습니다.벨만-포드 알고리즘은 음수 사이클의 존재 여부를 확인할 수 있습니다.시간 복잡도:O(V×E)O(V \times E)O(V×E), 여기서 V..
자료구조&알고리즘/C++
2025. 1. 13. 19:00
