벨만 포드1 벨만-포드 (Bellman-Ford) 오늘은 최단 경로를 찾는 대표적인 기법 중 하나인 벨만-포드 알고리즘을 알아보려 합니다. 벨만-포드는 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점 S 에서부터 다른 정점까지의 최단경로 (1:N) 를 구하는 알고리즘입니다. 다익스트라와 달리 음의 가중치를 가진 간선을 가질 수 있고, 때문에 음의 사이클의 존재 여부를 확인해주어야 합니다. 최단거리를 구하기 위해 최대 (V-1)번 E개의 모든 간선을 확인하고, 음의 사이클을 확인하기 위해 한 번 더 E개의 간선을 확인합니다. 따라서 벨만-포드 알고리즘은 O(VE)의 시간복잡도를 가지게 됩니다. 구체적인 벨만-포드 Swift 코드를 보기 전에, 벨만-포드 알고리즘의 구현을 슈도 코드(Pseudo Code)로 먼저 보겠습니다. 슈도 코드.. 2021. 3. 8. 이전 1 다음
