벨만 포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같음기능특징시간 복잡도(노드: V, 에지: E)특정 출발 노드에서 다른 모든 노드까지의 최단 경로- 음수 가중치 간선이 있어도 수행- 음수 사이클의 존재 여부 판단 가능O(VE)핵심 이론벨만 포드 알고리즘은 다음 3단계의 원리로 동작1. 에지 리스트로 그래프 표현 및 최단 경로 배열 초기화벨만 포드 알고리즘은 간선을 중심으로 동작하므로 그래프를 간선 리스트로 구현또한 최단 경로 배열은 출발 노드는 0, 나머지는 무한대로 초기화2. 모든 에지를 확인해 정답 배열 갱신최단 거리 배열에서 갱신 반복 횟수는 노드 개수 -1∵ 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 간선의 최대개..