벨만-포드(bellman-ford moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다. 기능 특징 시간 복잡도 (V: 노드 수, E: 에지 수) 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 - 음수 가중치 에지가 있어도 수행할 수 있음. - 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음. O(VE) 벨만 - 포드의 핵심 이론 아래 3가지 단계로 동작합니다. 1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화. 벨만-포드 알고리즘은 에지를 중심으로 동작하여 에지 리스트로 구현합니다. 다익스트라와 똑같이 출발 노드는 0, 다른 노드들은 ∞ 로 초기화합니다. 아래 그래프의 예에서 출발 노드는 1로 하여 벨만-포드 알고리즘을 진행해보겠습니다. 2. 모든 에지를 ..
