벨만 - 포드 알고리즘 ( Bellman - Ford Algorithm ) 
 다익스트라 처럼 벨 만 - 포드 알고리즘 도 1 개 의 시작 정점 을 기준 으로 모든 정점 까지 도달 하 는 데 최단 거리 를 구하 는 알고리즘 입니다 . 하지만 , 다익스트라 와 는 다르 게 음수 간선 이 포함 되 어 있 어도 최 단거리 를 정상 적 으로 구할 수 있 으며 음수 사이클 이 있 는지 또한 확인 이 가능 합니다 . 다만 , 다익스트라 에 비해 속도 가 느리 므로 그래프 에 음수 간선 이 존재 하 지 않 고 다 익스 트 트라 로 충분히 해결 가능 한 문제 라면 다익스트라 를 사용 하 는 것 이 더 효율 적 입니다 . 
 벨 만 - 포드 는 다익스트라 와 비슷 하 게 거리 를 저장 할 배열 ( dist ) 를 만들 고 매번 거리 를 갱신 합니다 . 차이점 이 있 다면 다익스트라 는 우선 순위 큐 를 사용 하 여 연결 된 가장 가까운 정점 을 이용 하 여 정점 의 거리 를 갱신 했 다면 벨 만 - 포드 는 모든 간선 을 여러 번 확인 하 여 최단 거리 를 갱신 하 는 방식 입니다 . 
 만약 간선 e 가 있 고 간선 e 는 정점 u 와 v 를 잇 는다고 할 때 dist [ v ] 가 dist [ u ] + weight [ e ] 보다 크 다면 지금 까지 구한 정점 v 로 가 는 최단 경로 보다 정점 u 를 거쳐 가 는 최단 경로 가 더 빠르 므로 이 때 최단 거리 를 갱신 해 주 면 됩니다 . 시작점 에서 임의 의 정점 u 로 가 는 데 거쳐야할 간선 의 개수 는 최대 V - 1 개 입니다 . 그런데 벨 만 - 포드 는 위 의 작업 을 V 번 반복 합니다 ! 
 물론 V - 1 번 작업 을 반복 해도 최단 거리 는 충분히 구할 수 있 습니다 . 하지만 굳이 한 번 을 더 하 는 이유 는 음수 사이클 의 존재 를 확인 하 기 위한 것 인데 , 음수 사이클 이 있 다는 것 은 무한정 최단 거리 가 갱신 된다는 뜻 이 기 때문 에 V - 1 번 위 작업 을 반복 하 여 최단 거리 를 구했 음 에 도 불고 하 고 한번 더 작업 을 반복 했 을 때 거리 가 변경 된다면 음수 사이클 이 있 다는 것 을 의미 합니다 . 
 BOJ 11657 번 문제 를 벨 만 - 포드 알고리즘 을 이용 하 여 해결 하 는 코드 는 아래 와 같 습니다 . 
 간선 구 조체 Edge 정의 
 Edge -> from : 간선 의 시작 정점 
 Edge -> to : 간선 의 도착 정점 
 Edge -> cost : 간선 의 가중치 
 / / 정점 수 와 간선 의 수 를 입력 받 음 
 / / 거리 배열 을 INF 값 으로 초기 화 
 / / 간선 정보 를 입력 받 고 배열 에 저장 
 / / 시작 정점 으로 가 는 거리 는 0 이 다 
 / / 최단 거리 를 찾 는 작업 을 V 번 반복 한다 
 / / 모든 간선 을 확인 한다 
 / / 정점 from 에 대한 최단 거리 가 이미 계산 되 었 으며 
 / / 정점 from 을 통해 정점 to 로 가 는 것 이 더 빠른 경우 거리 를 갱신 
 / / 모든 정점 에 대해 최 단거리 가 계산 된 상태 인데 도 계속 값 이 갱신 된다면 음수 사이클 이 존재 함 을 의미 
 / / 정답 출력