1. 개요벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 출발점으로부터 다른 정점 사이의 최단 거리를 구하는 알고리즘입니다. 다익스트라 알고리즘은 가중치가 음수인 간선이 있는 그래프에서 최단 거리를 계산하는 것이 불가능합니다. 벨만-포드 알고리즘은 다익스트라 알고리즘에 비해 시간적 성능은 떨어지지만 가중치가 음수인 간선이 존재하는 그래프에서도 최단 거리를 구하는 것을 보장합니다. 벨만-포드 알고리즘은 가중치가 음수인 그래프의 최단 거리를 구할 순 있으나 negative cycle이 존재하는 그래프의 최단 거리를 구하는 것은 불가능합니다. 그 이유는 탐색을 반복할수록 출발점에서 negative cycle 내 정점들까지의 최단 거리는 무한히 감소하기 때문입니다.위에 그래프 예시에서 1번 정점을 출발점으로 ..
