개요
가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구할수 있는 알고리즘.
Dijkstra's Algorithm과 같지만, 음의 가중치를 갖는 그래프에서도 사용가능하다.
다만, 음의 cycle을 갖는 그래프에서는 사용불가하다. (문제로서 성립되지 못하기때문에)
그래프를 bfs순회처럼 v1에서 hop을 뛰어넘으면서 최단경로를 갱신해나가는 방법이다.
BellmanFord Algorithm
// vertices : 정점 리스트
// edges : 간선 리스트
// source : 시작점 위치
// distance : 시작점으로부터 vi까지 최단경로길이
// predecessor : 시작점으로부터 vi까지 최단경로에서 vi이전정점(부모정점)
function BellmanFord(list vertices, list edges, vertex source) :: distance[], predecessor[]
{
// step 1: initialize graph
for each vertex v in vertices:
distance[v] := INF // v1으로부터 거리를 INF로 초기화
predecessor[v] := null // 부모는 초기값으로 없음
distance[source] := 0
// step 2: relax edges repeatedly : O(|V||E|)
for i from size(vertices)-1:
for each edge(u, v) with weight w in edges: // 그래프의 모든 edge를 순회하면서
if distance[u] + w < distance[v]: // 최적화 할수있는 경우를 찾는다.
distance[v] := distance[u] + w
predecessor[v] := u
// step 2': relax edges repeatedly by queue (Shortest Path Faster Algorithm)
push source in Q
while Q is not empty:
u := deque Q
for each edge(u, v) in E(G): // u와 연결된 Edge들을 순회한다.
if distance[u] + w < distance[v]: // 최적화 할수 있는 경우를 찾는다.
distance[v] := distance[u] + w
predecessor[v] := u
// step 3: ONLY WHEN you want to check for negative-weight cycles
for each edge(u, v) with weight w in edges: //
if distance[u] + w < distance[v]:
error "Graph contains a negative-weight cycle"
return distance[], predecessor[]
}
Complexity
$O(|V||E|)$
여담
Step 2'와 같이 Queue를 이용하여 구현했을경우, 음의 cycle이 존재하면 무한루프를 돌게된다.
Step 3의 방법으로 그래프 내에 음의 cycle을 찾아낼수 있지만, 알고리즘 문제에서 적용가능한지는 생각해봐야한다.
만약 시작지점과 목적지가 결정된 문제라면, 구해낸 최단경로에 포함되지 않은 장소에 음의 cycle이 존재할수 있을수 있기 때문이다.