ps:전체쌍_최단_경로
전체쌍 최단 경로 (All-pairs shortest path)
- 위키피디아 참고
- 진짜로 O(n^2)개의 모든 페어에 대해서 전부 구해야 하는 문제가 있고, 그 정도까지는 아니고 Q개의 쿼리에 대해서 구해야 하는 문제가 있을수 있다.
- 트리에서는 LCA를 이용해서 처리할 수 있다. 루트에서 각 노드까지의 거리를 미리 O(N)에 구해둔다면, u에서 v까지의 거리는 d(U,V) = d(root,U) +d(root,V) - d(root,lca)*2 로 구할수 있다. 쿼리당 걸리는 시간은 lca에 걸리는 시간과 동일하다.
- LCA를 구하는 방법이 여러가지인데, Q가 N과 비슷한 크기라면, HLD에 기반한 방법이 실질적으로 가장 빠르다. O(N)에 전처리를 한 뒤, O(logN)에 쿼리를 처리하게 되므로 시간복잡도는 O(N+QlogN) 이다
- 전체 페어에 대해서 거리를 모두 구하거나.. 그정도는 아니라도 Q가 크다면, sparse table을 이용해서 O(NlogN)에 전처리하고 O(1)에 LCA 쿼리를 처리하는 방식을 써야 한다. O(N^2) 또는 O(Q) 에 처리 가능하다.
- 참고문제: 1761
- 트리가 아닌 그래프에서는 쿼리에 특화된 방법은 없고, 그냥 전체 페어에 대해 다 계산하는게 최선이다.
- 단일 출발지 최단 경로 (Single Source Shortest Path) 알고리즘을 모든 노드에서 돌려서 푸는 방법과, 플로이드-와샬 알고리즘을 사용하는 방법이 있다.
- 플로이드-와샬 알고리즘의 시간복잡도는 O(V^3)이고, 코드가 간단하고 상수값이 작은 편이라서, 다른 방법으로도 O(V^3)이 나온다면 플로이드 알고리즘을 쓰는 것이 유리하다
- 구체적인 예를 생각해보자
- 가중치 없는 그래프:
- 그래프가 sparse 하다 ⇒ V번의 BFS.
- BFS로 단일출발지 최단 경로를 구하는 데에는 O(E)가 걸리고, V번 반복하는데에는 O(EV)가 걸린다. 플로이드보다 유리하다
- 그래프가 dense 하다 ⇒ V번의 dense BFS
- dense 그래프에서는 V번의 BFS로 얻은 O(EV)가 플로이드의 O(V^3)보다 빠르지 않으므로 플로이드를 써야 할것 같다.
- 하지만 dense BFS를 이용하면 단일출발지 최단 경로를 O(V)에 구할수 있으므로, 총 O(V^2)이 걸려서 플로이드보다 빠르다.
- 양수 가중치만 갖는 그래프
- 그래프가 sparse하다 ⇒ V번의 데이크스트라
- 데이크스트라로 단일출발지 최단 경로를 구하는데에 O(ElogV)가 걸리고 V번 반복하는데에는 O(VElogV)가 걸린다. |E|<(V^2)/logV 이면 플로이드의 O(V^3)보다 빠르다. 플로이드의 상수가 작은 것을 고려하면, 그래프가 많이 sparse해야 한다.
- 그래프가 dense하다 ⇒ 플로이드
- dense 그래프라면, 힙을 안쓰는 버전의 데이크스트라를 쓰는 것이 유리하다. 그러면 O(V^2)을 V번 반복하므로 O(V^3). 플로이드보다 빠르지 않으므로, 그냥 플로이드를 쓴다
- 음수 가중치도 갖는 그래프
- 그래프가 sparse하다 ⇒ 존슨 알고리즘
- 그래프가 sparse 하더라도, 벨만-포드나 SPFA로 단일출발지 최단 경로를 구하게 된다면 O(VE)가 걸리고, 이것을 모든 노드에 돌리면 O(V^2E)로 느리므로, 플로이드를 써야 할것 같다
- 하지만, 존슨 알고리즘을 이용하면, O(VE)에 양수 그래프로 변환한 뒤에 데이크스트라를 V번 돌리는 것으로 처리할수 있다. 총 O(VElogV)가 걸리므로 플로이드보다 빠르다
- 그래프가 dense하다 ⇒ 플로이드
플로이드-와샬 알고리즘
- 위키 에 의하면 빠른 행렬곱 연산을 이용해서 속도를 높이는 방법이 있다고 한다. 그렇지만 상수항이 커서 아주 큰 그래프에서만 효과있다고 한다. 아마도 PS에서는 신경안써도 될거 같다
- 음수 가중치 엣지가 있는 그래프에서도 잘 동작한다. 만약 음수 사이클이 있는지를 체크하고 싶다면 dist[u][u]<0 이 되는 u가 있는지를 찾으면 된다.
- 인접행렬 형태로 주어진 그래프에서 O(|V|^3)에 계산된다. 하지만 코드가 매우 심플하고 상수항이 작다는 특징이 있다. dense한 그래프에서는 단일 출발지 최단 경로를 찾을때에도 O(|V||E|)인 벨만포드 알고리즘보다 더 빠르게 수행되는 경우도 있다고 한다
구현
- 그래프가 인접행렬 형태로 주어지면 바로 실행할 수 있지만, 인접리스트 형태를 사용하는 다른 그래프 알고리즘과 일관성이 안맞는 문제가 있다. 일단은 인접행렬을 인자로 받게 만들었다. 필요하면 사용자가 인접리스트를 인접행렬로 변환해서 돌리도록 했다.
- path reconstruction이 필요할 경우도 있는데.. 지금은 고려 안함. 필요하면 나중에 생각해보겠음..
코드
관련 문제
ps/전체쌍_최단_경로.txt · 마지막으로 수정됨: 2024/03/13 13:52 저자 teferi
토론