Johnson's 알고리즘이란?
목적
앞서 설명한 FloydWarshall처럼 APSP(All-Pairs Shortest Paths)를 계산할 때 사용된다.
다만 FloydWarshall보다 시간 복잡도를 조금 더 줄이고자 생긴 Algorithm이다.
Sparse한 Graph에서는 훨씬 더 나은 시간 복잡도를 가진, APSP를 계산하는 알고리즘이다.
물론 negative edge들도 사용할 수 있다.
사전 지식
시작하기에 앞서, reweighting 작업이 필요하다.
이 알고리즘은 빠른 속도를 위해 Dijkstra를 일부 사용할 것이다. 그 조건으로 negative edge들을 모두 없애야 한다.
하지만 앞서 설명했듯이 단순히 값을 더하는 것으로는 최단거리를 찾을 수 없다. 그렇다면 어떻게 해야할까?
바로 새롭게 정의하는 것이다.
이 사진을 보면, 새로운 length l'을 l+p_s - p_t로 설정한다. 이렇게 되면 path를 계산해도 l+p_s - p_t가 되어 결국 고정된 s, t에 대해서는 최단거리 경로가 변하지 않는다. (물론 경로 자체는 변할 수 있다.)
이렇게 새로운 s를 정의하고, 각 s에서 모든 vertex까지의 거리를 0으로 설정한다. 그리고 vertex weight p_v를 s-v path의 최단거리로 설정한다.
이렇게 하는 이유는 바로
앞서 설명한 방법을 사용해 새로운 edge length를 정의하면 모두 음이 아닌 값이 되기 때문이다! 이 방법을 통해 우리는 이제 Dijkstra를 사용할 수 있다.
왜 이게 될까?
천천히 살펴보자. p_u, p_v는 각각 s로부터의 최단거리이다. 이는 BellmanFord로 찾을 것이다.
이제 새로운 edge length l' = l_uv + p_u - p_v를 살펴보자. p_u + l은 l_uv에 p_u를 더한 것이다.
이는 P를 최단거리 s-u path라 했을 때, P에서 (u,v) edge를 추가한 것이다. 즉, s-u-v path를 의미한다. 이 값은 정의상 p_v보다 크거나 같아야 한다.
왜냐하면 p_v는 s에서 v까지의 최단거리이고, l_uv + p_u는 s에서 u까지의 최단거리에 uv edge 길이를 더한 것이기 때문이다.
따라서, 이항을 하면 항상 성립함을 알 수 있다!
알고리즘 설명
전반적인 알고리즘이다.
1) 새로운 s를 설정해 모든 vertex까지의 거리를 0으로 설정한다.
2) BellmanFord를 vertex s를 기준으로 사용한다. (만일 negative cycle이 있다면 멈춘다)
3) 모든 vertex에 대해, p_v를 s로부터 v까지의 최단거리로 설정하고, 새로운 edge length l을 정의한다.
4) 이 새로운 edge length를 edge로 하는 그래프에 Dijkstra 알고리즘을 실행한다.
5) 찾은 값들은 새로운 edge length 기준이므로 다시 원래대로 복구하여 최종적인 edge들을 계산한다.
시간 복잡도
총 Running time은 무려 O(VE*log(V))로, sparse graph에 대해서 FloydWarshall보다 더 뛰어난 성능을 보여준다.
