[그래프] 벨만-포드 알고리즘

 

벨만 - 포드 알고리즘은 그래프에서 간선의 가중치가 음의 값을 허용하는 임의의 실수인 경우 최단 경로를 찾는 알고리즘이다.

즉, 음의 가중치를 허용할 때 최단 경로를 찾는 알고리즘이다. 

 

벨만 - 포드 알고리즘은 간선을 최대 1개 사용하는 경로에서 최대 n-1개 사용하는 최단 경로까지 구해나간다.

 

//벨만-포드 알고리즘
// G: 그래프 V:정점(vertex) E:간선(edge) r: 시작 정점
BellmanFord(G,r)
{
    for each u∈V
    	d[u] <- ∞;
    d[r] <- 0;
    
    for i <- 1 to |V|-1
    	for each (u,v) ∈ E
        	if(d[u]+w(u,v) < d[v]) then {
            	d[v] <- d[u]+w(u,v);
                prev[v] <- u;
            }
     
     for each(u,v) ∈ E
     	if(d[u]+w(u,v) < d[v]) then output "음의 사이클 발견! 해 없음";
}

첫번째로 등장하는 for문이 이 알고리즘의 핵심부분이라고 볼 수 있다. 

 

첫번째 for문은 총 n-1번 반복된다. i번째 루프가 끝나면 최대 i개의 간선을 사용해서 이를 수 있는 최단 경로가 계산된다.

for문을 시작하기 전에는 경로를 사용할수 없기 때문에 도달할 수 있는 정점은 자기 자신 뿐이고, 따라서 r의 최단거리만 0이 되고 나머지는 모두 ∞로 초기화 되었다. n-1번째 루프가 끝나게 되면 최대 n-1개의 간선을 사용해서 이를 수 있는 최단 경로가 계산되고, 이 경로가 이 그래프의 최단 경로가 된다. 

 

n-1개보다 많은 간선을 사용하는 경우에는 적어도 하나의 사이클이 존재하게 된다. 최단 경로 문제의 정의에서 음의 사이클은 존재할 수 없으므로 이 사이클은 절대 음이 아니다. 따라서 n-1개 이하의 간선을 사용하는 최단 경로 중에서 최종 최단 경로가 존재하게 된다. 

 

 

[참고] 책 쉽게 배우는 알고리즘