[그래프 알고리즘]존슨 알고리즘(플로이드워셜보다 좋은 이유)

존슨 알고리즘의 특징

존슨 알고리즘은 그래프에서 모든 노드 쌍간의 최단거리를 구하는 알고리즘입니다.

기본적인 아이디어는 모든 노드에 대하여 다익스트라 알고리즘을 수행하는 것입니다.

하지만, 다익스트라 알고리즘은 음이 아닌 가중치의 엣지에서만 작동하므로,

다익스트라 알고리즘을 적용하기 전에 엣지들의 가중치를 음수가 되지 않도록 변환해야 합니다.

이 변환을 위해 벨만포드 알고리즘이 사용됩니다.

새로운 가중치 부여

그래프에 새로운 노드 s를 추가합니다.

그리고 노드 s를 다른 모든 노드에 가중치 0으로 연결합니다.

벨만포드 알고리즘을 이용해서 노드 s로 부터 나머지 노드로의 최단거리 리스트 h를 구합니다.

이제 모든 엣지의 가중치를 다음과 같이 새로 부여합니다.

 

new weight(u, v) = weight(u, v) + h[u] - h[v]

 

이렇게 변환하면, 임의의 두 노드 사이의 엣지들의 가중치 총 합이 다음과 같이 간단히 계산됩니다.

 

new weight(u1, uN) = new weight(u1, u2) + new weight(u2, u3) + ... + new weight(uN-1, uN)

= weight(u1, u2) + h[u1] - h[u2] + weight(u2, u3) + h[u2] - h[u3] + ... + weight(uN-1, uN) + h[uN-1] - h[uN]

= weight(u1, u2) + weight(u2, u3) + ... + weight(uN-1, uN) + h[u1] - h[uN]

 

임의의 두 노드 u, v 사이의 새로운 가중치 총 합은, 기존의 가중치 총 합에 h[u] - h[v]만 더해주면 됩니다.

그러면 엣지들의 새로운 가중치는 모두 음이 아님이 보장되는데, 그 이유는 벨만 포드 알고리즘을 수행하면서 다음을 만족하기 때문입니다.

 

h[v] <= weight(u, v) + h[u]

 

식을 변형하면 0 <= weight(u, v) + h[u] - h[v] 를 만족함을 알 수 있습니다.

이제 새롭게 부여된 가중치로 모든 노드에 대해 다익스트라 알고리즘을 수행하면 됩니다.

구현

다익스트라 알고리즘으로 한 노드에서 다른 노드들로의 최단 거리를 구한 뒤 h[v] - h[u]를 더해 다시 원래 가중치로 되돌려 놓는 것을 확인할 수 있습니다.

플로이드 워셜과의 비교

플로이드 워셜 알고리즘도 대표적인 모든 쌍 최단거리를 구하는 알고리즘입니다.

하지만 그래프를 구현하기 위해 인접 행렬을 사용해야 하고 시간복잡도가 O(V^3)이므로, 노드가 매우 많은 경우에는

시간과 메모리가 많이 필요합니다.

하지만 존슨 알고리즘은 인접 리스트가 사용 가능하고, 시간 복잡도도 O(V^2 log(V) + VE)로 알려져 있습니다.

벨만포드 알고리즘을 수행하는 O(VE)와 모든 노드에 대하여 다익스트라 알고리즘을 수행하는 O(V^2logV)의 합입니다.

따라서 노드가 매우 많으면서 엣지는 적은 희소 그래프의 경유는 모든 쌍 최단 거리를 구하기 위해 존슨 알고리즘을 적용하는 것이 더 나을 수 있습니다.