벨만-포드 알고리즘 벨만 포드에서 넘어옴. #벨만 포드 [ 수정 내역 ] [ 수정 ]

최근 수정: 4년 전

1. 개요

Bellman - Ford Algorithm.

알고리즘을 만든 사람의 이름을 따서 벨만-포드라 한다.

2. 상세

최단 경로 알고리즘 중 하나. 다이나믹 프로그래밍 방식을 사용하여 최단 경로를 계산한다. 특히, 다익스트라와 다르게 음수 가중치가 있는 그래프에도 사용할 수 있으며, 음수 사이클도 탐지 가능하다는 매우 큰 장점이 있다.

3. 구현

다이나믹 프로그래밍 방식을 사용한다. 점화식은 아래와 같다.

distance[i] : i번 정점 까지의 최단 경로.
distance[i] = min(distance[i], distance[j] + (j 에서 i까지 간선의 가중치));

배열을 사용하는데, distance[i]는 시작 정점부터 i번 정점까지의 최단 경로를 의미한다. 그리고 for문을 이용하여 아래 식을 반복하여 계산해주면 된다. distance[j] + j 에서 i까지 간선의 가중치의 의미는 시작 정점으로부터 j번 정점을 거쳐 i번 정점으로 가는 경로를 의미한다.

이런 2가지 연산을 모든 정점과 간선에 대해 차례로 돌리면서 값을 업데이트하면 된다.

4. 음수 사이클 탐지

경로에는 사이클이 없으므로 최대로 거쳐갈 수 있는 정점의 개수는 V - 1 (정점의 개수 - 1)개 이다. 따라서 V번 반복했는데도 distance 배열에 업데이트가 발생했다면 음수 사이클이 발생한 것이다.

5. 같이 보기

알고리즘 프로젝트

최단 경로