벨만 포드 알고리즘(The Bellman-Ford algorithm)

알고리즘 정의

하나의 시작점에서 하나의 도착점으로 가는 최단경로 문제를 해결하는 알고리즘이다.

특징

음의 간선이 있는 경우에도 문제를 해결한다.

 

수도코드

Bellman-Ford(G,w,s)
	Initialize-Single-source(G,s)
    	for i<-1 to |V[G]|-1
			do for each edge(u,v) <- E[G]
            	do RELAX(u,v,w)
			for each edge(u,v) <- E[G]
            do if d[v] > d[u] + w(u,v)
					then return FALSE
	return TRUE

 

Relaxation order을 통해 어떤 간선부터 추가를 할지 정한다.

 

 

초기에 출발 정점을 제외한 다른 모든 정점의 초기값은 무한이다.

 

 

 

S를 기준으로 도달가능한 정점으로는 t,y가 있다.

t와 y를 업데이트하면,

 

 

t는 6, y는 7로 업데이트 된다.

 

t와 y를 기준으로 매번 relaxation을 수행해주게 된다.

vertex가 추가될 때마다 매번 모든 간선들에 대해서 relaxation을 다 반복한다.

 

 

 

 

x와  z가 연결된 상황에서 다시 연결가능한 모든 상황을 체크해 본다.

 

 

 

z에서 s로 가는 건 의미가 없고,
z에서 x로 가는 간선을 고려하면 2+7이 되서 지금 있는 4보다 크게 되므로 필요가 없다.
x에서 t로 가는 것만 고려해주면 된다.

 

새로운 경로가 또 생겼기 때문에 t를 기준으로 다시 한번 더 relaxation해준다.

 

 

시간복잡도
O(VE)

vertex가 하나 추가될때마다 모든 edge를 다 확인(relaxation)한다.