이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자. 벨만포드(Bellman-Ford) 알고리즘 다익스트라의 한계이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다. 벨만포드 알고리즘벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다.벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최단 거..