ps:이론:apsp
목차
전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP)
- 위키피디아 참고
- 그래프의 모든 정점쌍 사이의 최단 경로를 전부 구하는 문제이다.
- Q개의 정점쌍에 대해서 최단 경로를 구해야 하는 문제나 (Q가 거의 n^2에 가깝게 크게 들어온다), 모든 정점쌍 사이의 거리중에서 최적값을 찾는 등의 문제가 있다.
- 모든 정점쌍 사이의 최단 경로를 구하는 알고리즘은 대표적으로는 플로이드-와샬 알고리즘이 있지만, 단일 출발지 최단 경로 (Single Source Shortest Path) 알고리즘을 모든 정점에 대해서 돌리는 방법도 가능하고, 경우에 따라서는 그쪽이 더 효율적인 경우도 있다.
- 하지만 웬만하면 그냥 무지성으로 플로이드-와샬 알고리즘을 돌려도 거의 다 풀린다.
- 그리고 Solved.ac 에서는 '전체쌍 최단 경로'라는 태그는 따로 없고, 대신 관련 문제에는 모두 '플로이드-와샬' 태그가 붙어 있다.
플로이드-와샬 알고리즘
- 기본 난이도: 골드5
- 기본 문제: 플로이드
- 필요한 사전 지식: 그래프
- 가중치의 범위 (가중치 없음, 양수 가중치, 양수와 음수를 모두 포함하는 가중치)에 관계없이 모두 적용가능한 알고리즘이다.
- 음수 사이클이 있는지를 체크하는 용도로도 사용 가능하다.
- 시간복잡도는 O(V^3). 하지만 코드가 매우 심플하고 상수항이 작다는 특징이 있다. dense한 그래프에서는 단일 출발지 최단 경로를 찾을때에도 O(|V||E|)인 벨만포드 알고리즘보다 더 빠르게 수행되는 경우도 있다고 한다
- 하지만, 코드가 간단한것에 비해, 정확한 동작 원리를 이해하는 것은 그렇게 간단하지 않다. 실제로 구현해야 할때는 3중루프의 순서를 헷갈리지 않는것도 중요하다. 보통은 루프 인덱스 변수를 k,i,j 순서로 사용하고, d[i][j] = min(d[i][k]+d[k][j], d[i][j]) 와 같은 식으로 갱신하는 것이 일반적이다.
구현
- 그래프가 인접행렬 형태로 주어지면 바로 실행할 수 있지만, 인접리스트 형태를 사용하는 다른 그래프 알고리즘과 일관성이 안맞는 문제가 있다. 일단은 인접행렬을 인자로 받게 만들었다. 필요하면 사용자가 인접리스트를 인접행렬로 변환해서 돌리도록 했다.
- path reconstruction은 좀 복잡하다. 이게 필요하면 그냥 플로이드 대신 데이크스트라 V번 돌리는 식으로 해결하자
- 무방향 그래프라면, dist(i,j)와 dist(j,i)를 동시에 업데이트해줄 수 있으므로, 루프 횟수를 절반으로 줄일 수 있다.
코드
관련 문제
트리에서의 전체쌍 최단 경로
- 기본 난이도: 플래티넘5
- 기본 문제: 1761
- 필요한 사전 지식: 최소 공통 조상 (Lowest Common Ancestor / LCA)
- 웬만한 형태의 그래프에서는 그냥 플로이드를 돌려도 최적 시간복잡도에 근접하므로 시간초과가 나는 경우는 거의 없지만, 트리에서는 플로이드를 돌리는 것이 비효율적이다.
- 모든 정점쌍에 대해서 최단경로가 필요한 경우
- V번의 BFS/DFS 를 사용하자
- 트리에서는 두 점사이의 경로가 유일하기 때문에 BFS/DFS로도 O(V)에 단일 출발지 최단 경로를 구할수 있다. V개의 시작점에 대해서 돌리면 총 O(V^2). 플로이드보다 훨씬 효율적이다.
- Q개의 정점쌍에 대한 최단 거리만 필요
- 트리에서는 두 점사이의 경로가 유일하고, 그 경로의 길이는 경로상의 엣지들의 가중치의 합이므로, 두 점사이의 최단거리는 단순한 형태의 경로 쿼리가 된다. 이것은 LCA를 이용해서 구할 수 있다. 루트에서 각 노드까지의 거리를 미리 O(V)에 구해둔다면, u에서 v까지의 거리는 d(U,V) = d(root,U) +d(root,V) - d(root,lca)*2 로 구할수 있다. 쿼리당 걸리는 시간은 lca를 구하는데에 걸리는 시간과 동일하다.
- LCA를 구하는 방법은 여러가지가 있지만, Q가 V와 비슷한 크기라면, HLD에 기반한 방법이 실질적으로 가장 빠르다. O(V)에 전처리를 한 뒤, O(logV)에 쿼리를 처리하게 되므로 시간복잡도는 O(V+QlogV) 이다.
- Q가 크다면, LCA를 sparse table을 이용해서 처리하는 것이 더 빠를수 있다. 전처리에 O(VlogV)이 걸리고, O(1)에 LCA를 구할수 있다. 총 시간복잡도는 O(VlogV + Q)
단일 출발지 최단 경로를 반복해서 풀기
- 기본 난이도: not rated
- 필요한 사전 지식: SSSP
- 트리가 아니더라도, 그래프의 상태에 따라서 SSSP 알고리즘을 모든 정점에 대해서 돌리는 것이 플로이드-와샬 보다 효율적인 경우가 있다.
- 시간복잡도는 단일출발지 최단경로를 구하는 데에 O(T)가 걸린다면, 총 O(VT)가 된다. 이것이 플로이드의 O(V^3)보다 작으면 이쪽을 쓰는것이 유리하다.
- 만약 똑같이 O(V^3)이 걸린다면, 플로이드가 코드가 간단하고 상수값이 작은 편이므로 그냥 플로이드를 쓰는 것이 낫다.
- 구체적인 예를 생각해보자
- 가중치 없는 그래프
- 그래프가 sparse 하다 ⇒ V번의 BFS.
- BFS로 단일출발지 최단 경로를 구하는 데에는 O(E)가 걸리고, V번 반복하는데에는 O(EV)가 걸린다. E « V^2 일때는 플로이드보다 유리하다
- 그래프가 sparse하지 않다 ⇒ 플로이드.
- 그래프가 매우 dense 하다 ⇒ V번의 dense BFS
- 사실 해본적은 없는데, dense BFS 를 이용하면 빠를거 같다. O(E)에 complement graph를 만들수 있고, 그 위에서 dense bfs를 돌리는 것은 O(E')에 구할수 있다 (E' = complement graph의 에지수). 총 O(E + VE')이 걸리니까, E'이 작으면 플로이드보다 빠르다.
- 양수 가중치만 갖는 그래프
- 그래프가 sparse하다 ⇒ V번의 데이크스트라
- 데이크스트라로 단일출발지 최단 경로를 구하는데에 O(ElogV)가 걸리고 V번 반복하는데에는 O(VElogV)가 걸린다. |E|<(V^2)/logV 이면 플로이드의 O(V^3)보다 빠르다. 플로이드의 상수가 작은 것을 고려하면, 그래프가 많이 sparse해야 한다.
- 그래프가 dense하다 ⇒ 플로이드
- dense 그래프라면, 단일출발지 최단 경로를 구할때에 힙을 안쓰는 버전의 O(V^2) 데이크스트라를 쓰는 것이 유리하다. 그렇다 해도 전체 시간복잡도는 O(V^2)을 V번 반복하므로 O(V^3). 플로이드보다 빠르지 않으므로, 그냥 플로이드를 쓴다
- 음수 가중치도 갖는 그래프
- 그래프가 sparse하다 ⇒ 존슨 알고리즘
- 그래프가 sparse 하더라도, 벨만-포드나 SPFA로 단일출발지 최단 경로를 구하게 된다면 O(VE)가 걸리고, 이것을 모든 노드에 돌리면 O(V^2E)로 느리므로, 플로이드를 써야 할것 같다
- 하지만, 존슨 알고리즘을 이용하면, O(VE)에 양수 그래프로 변환한 뒤에 데이크스트라를 V번 돌리는 것으로 처리할수 있다. 총 O(VElogV)가 걸리므로 플로이드보다 빠르다
- 그래프가 sparse하지 않다 ⇒ 플로이드
활용
그래프의 지름, 반지름, 중심
- 트리에서는 두번의 DFS로 지름, 반지름을 찾을수 있지만, 일반 그래프에서는 그러한 간단한 방법은 없다.
- 다소 무식해 보이지만, 전체쌍 최단 경로 문제로 변환해서 모든 dist(u,v)를 구한 뒤에 다음처럼 계산하는 것이 최선이다.
- 지름: $ \max_{u,v}{dist(u,v)} $
- 반지름: $ \min_u\max_v{dist(u,v)} $
- 중심: $ \text{argmin}_u\max_v{dist(u,v)} $
- Median: $ \min_u \sum_v dist(s, t) $
- 관련문제:
- 2660: 센터와 반지름
Transitive closure
- [To be filled] 비트셋을 쓰자!
- 관련문제: 2458, 10159, 1613
APSP conjecture
- APSP 문제는 다항시간에 풀리기는 하지만, O(n^3)이라는 꽤 큰 시간이 드는, 아주 쉽지는 않은 문제다. 다른 문제들에 대해서도 문제가 어렵다는 것을 보이기 위해 (시간복잡도가 O(n^3)이상이라는 것을 증명하기 위해서), APSP 문제로 리덕션하는 접근법을 쓰는 경우가 있다고 한다.
- https://koosaga.com/310의 Theorem 6 에는 이러한 O(n^3) 이상이 걸리는 문제들이 나열되어있다. 나중에 이러한 문제들을 접하게 되면, 빠르게 푸는 방법을 찾으려 고생하지 말고, 그냥 APSP로 바꿔서 O(n^3)에 풀도록 하자.
- 앞에서 언급한 그래프의 반지름, 중심도 이 목록에 포함되어있다.
- 그래프의 지름의 경우는 더 쉬운 방법이 존재할수도 있지만, 아직 발견되지 않았다고 따로 언급되어있다.
ps/이론/apsp.txt · 마지막으로 수정됨: 2024/03/15 14:32 저자 teferi
토론