[알고리즘] 벨만-포드(백준 11657, 1865, 1219 -Java)

• 벨만-포드 알고리즘은 방향 그래프에서 가중치가 양수/음수일 때 출발 노드를 중심으로 최단거리를 구할 수 있는 알고리즘이며, 음수 사이클의 유무도 파악할 수 있다.

• 다익스트라 알고리즘과 비교했을 때, 벨만-포드 알고리즘은 가중치가 음수인 경우에도 사용 가능하다.

• 벨만-포드 알고리즘은 엣지를 중심으로 동작하며, 최단 경로 리스트를 출발 노드는 0, 나머지 노드는 무한으로 초기화한다.

• 음수 사이클을 확인하기 위해 모든 엣지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인하며, 업데이트되는 노드가 있다면 음수 사이클이 있다는 의미이다.