Bellman-ford algorithm(벨만 포드)

* Bellman-ford algorithm(벨만 포드) - 단일 출발점 최단 경로 알고리즘

  흔히 다익스트라와 비교되며, 다익스트라는 음의 사이클을 판단할 수 없지만, 벨만 포드는 완화(Relax) 절차를 이용하여 음의 사이클을 감지하여 최단경로가 존재할 수 없음을 알아낼 수 있다. 따라서 PS에서 음의 사이클이 존재할 가능성이 있고 단일 출발점 최단 경로를 구해야 한다면 다익스트라가 아니라 벨만 포드를 사용해야 한다.

  * 수식 표현

1. 델타(u, v) : u에서 시작해서 v까지의 최단 경로 길이

2. <v0, v1, ..., vk> : v0에서 vk로 가는 방문 정점을 담은 경로

3. v.d : 단일 출발점 s에서 시작해서 v까지의 계산된 경로의 길이

  * 완화(Relax) 특징

1. 삼각 부등식

임의의 간선 (u, v) ㅌ E에 대해 델타(s, v) <= 델타(s, u) + w(u, v)다.

2. 상한 특성 (중요)

모든 정점 v ㅌ V에 대해 항상 v.d >= 델타(s, v)이고, 일단 한 번 v.d가 델타(s, v)값에 도달하면 더이상 변하지 않는다. (음수 사이클 검출의 핵심 특징)

3. 무경로 특성

경로가 존재하지 않으면 v.d = 델타(s, v) = 무한대

4. 수렴 특성

s~>u->v가 최단 경로이고, 간선 (u, v)를 완화하기 전에 u.d = 델타(s, u)라면 v.d= 델타(s,v)이다.

5. 경로 완화 특성

p = <v0, v1, ..., vk>가 s=v0에성 vk까지의 최단 경로이고 p의 간선을 (v0, v1), (v1, v2), ... (vk-1, vk) 순서로 완화한다면 vk.d = 델타(s, vk)다.

6. 직전원소 부분 그래프 특성(중요)

모든 v ㅌ V에 대해 일단 한 번 v.d=델타(s, v)가 되면 직전 원소 부분 그래프는 s를 루트로 갖는 최단 경로들의 트리다.

* 벨만 포드

  벨만 포드는 이런 완화의 특징을 가지고 있다.  시간 복잡도는 총 O(VE)로써, 트리의 특징에 따라 최대 |V|-1개의 간선을 가질 수 있기에 전체 |V|-1번을 돌고, 각 반복에서는 해당 정점의 간선 수 |E|번 만큼 돌기 때문이다.

  델타(s, v)에서의 경로 p=<v0, v1, ..., vk>에서 s=v0이고, v=vk라고 할 때, |V|-1 반복에서 i=1,2,...,k에서 i번째 반복에서는 (vi-1, vi)가 완화된다.

 * 정확성

  |V|-1번 완화를 통해 s에서 도달 가능한 v ㅌ V는 모두 v.d = 델타(s, v)가 성립한다.

v.d = 델타(s, v)

    <= 델타(s, u) + w(u, v)

      = u.d + w(u, v)

  만약 음의 가중치를 갖는 순환을 포함한다면 이 순환 c=<v0, v1, ..., vk>고 v0=vk라고 한다면 아래 수식이 성립한다.

sigma(i=1 to k) w(vi-1, vi) < 0 (음수 사이클)

  따라서 이를 감지하기 위해서는 |V|번째에서도 완화가 발생했는지의 여부로 확인할 수 있다. 완화가 되었다면 음수 사이클이 존재함을 알 수 있다.

  * 구현

1. 정석

for (i = 0; i < V - 1; i++)
	for (j = 0; j < V; j++)
		for (Edge& e : adj[j])
			if (dist[e.v] > dist[j] + e.w) 
				dist[e.v] = dist[j] + e.w;

// |V|-1번 완화 이후, 모든 간선에 대해 완화가 존재할 수 있는지 확인
for (i = 0; i < V; i++)
	for (Edge& e : adj[i])
		if (dist[e.v] > dist[i] + e.w)
			negative_cycle = 1;

2. 축약

for (i = 0; i < V; i++)
	for (j = 0; j < V; j++)
		for (Edge& e : adj[j]) {
			if (dist[e.v] > dist[j] + e.w) {
				dist[e.v] = dist[j] + e.w;
				if (i == V - 1) // |V|번에서도 완화가 생기면 음수사이클이 존재
					negative_cycle = 1;
			}
		}