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
- 트리가 아닌 그래프에서는 쿼리에 특화된 방법은 없고, 그냥 전체 페어에 대해 다 계산해야 한다.
- 그래프가 sparse하고, 음수가중치가 없다면 단일 출발지 최단 경로 (Single Source Shortest Path) 알고리즘을 모든 노드에서 돌려서 푼다.
- 가중치 없는 그래프라면 O(E)의 BFS를 V번 돌려서 O(VE)가 되고, 양수 가중치를 갖는 그래프면 O(ElogV)의 다익스트라 알고리즘을 V번 돌려서 O(VElogV)에 풀수 있다.
- 그래프가 dense하거나, 음수 가중치를 갖는다면 플로이드-와샬 알고리즘을 사용한다. 시간복잡도는 O(V^3).
플로이드-와샬 알고리즘
- 위키 에 의하면 빠른 행렬곱 연산을 이용해서 속도를 높이는 방법이 있다고 한다. 그렇지만 상수항이 커서 아주 큰 그래프에서만 효과있다고 한다. 아마도 PS에서는 신경안써도 될거 같다
- 음수 가중치 엣지가 있는 그래프에서도 잘 동작한다. 만약 음수 사이클이 있는지를 체크하고 싶다면 dist[u][u]<0 이 되는 u가 있는지를 찾으면 된다.
- 인접행렬 형태로 주어진 그래프에서 O(|V|^3)에 계산된다. 하지만 코드가 매우 심플하고 상수항이 작다는 특징이 있다. dense한 그래프에서는 단일 출발지 최단 경로를 찾을때에도 O(|V||E|)인 벨만포드 알고리즘보다 더 빠르게 수행되는 경우도 있다고 한다
구현상 고려
- 입력값으로부터 그래프를 읽을때 인접행렬 형태로 읽어들이면 바로 수행할 수 있지만, 인접리스트 형태를 사용하는 다른 그래프 알고리즘과 일관성이 안맞는 문제가 있다.
- 결국 인접리스트 형태의 그래프를 입력으로 받도록 만들었다. 함수 내부에서 인접행렬 형태로 그래프를 변환한 후 그걸 기반으로 최단경로를 계산해서 테이블을 돌려준다
- path reconstruction이 필요할 경우도 있는데.. 지금은 고려 안함. 필요하면 나중에 생각해보겠음..
코드
각 노드에서 도착 가능한 노드를 찾을 경우
관련 문제
ps/전체쌍_최단_경로.txt · 마지막으로 수정됨: 2022/11/30 15:13 저자 teferi
토론