Bellman-Ford(벨만포드) 알고리즘은 음수 가중치가 있는 그래프에서 특정 시작점 Vs에서 다른 나머지 정점(Vi, i=1, N)까지의 최단거리를 구할 수 있는 알고리즘입니다. 이 벨만포드 알고리즘을 그래프의 음수 사이클의 존재 여부도 알 수 있죠. 1. 음수 가중치가 있는 그래프에서 시작점에서 다른 정점까지의 최단거리를 구할 수 있다. 2. 음수 사이클 존재 여부를 알 수 있다. Bellman-Ford 알고리즘의 동작과정은 각 정점들을 차례로 돌아 가면서 해당 정점의 간선들을 탐색합니다, 단 맨 처음은 시작점부터 탐색합니다. 그리고 그 간선의 가중치와 시작점에서 정점까지의 거리의 합이 해당 간선이 도달하고자 하는 정점의 기존 거리보다 작으면 업데이트합니다. 식으로 나타내면 다음과 같습니다. d[T]